Encontrando exemplos de idiomas "anti-palindrômicos"

Seja $\Sigma = \{ 0, 1 \}$ . Uma linguagem $L \subseteq \Sigma^*$ é dito ter a propriedade "anti-palíndromo" se por todos os textos $w$ que é um palíndromo, $w\notin L$ . Além disso, para cada string $u$ que não seja um palíndromo $u\in L$ ou $\mathrm{Reverse}(u) \in L$ , mas não ambos (!) (Exclusivo ou).

Entendo a propriedade anti-palíndromo, mas não consegui encontrar nenhum idioma que possua essa propriedade. O mais próximo que eu poderia encontrar é $\Sigma^* \setminus L$ , mas ele não tem o exclusivo ou parte ... que é, por exemplo, ambos e estão em .10 $01$$10$$L$

Alguém poderia me dar um exemplo de uma linguagem que possua essa propriedade? Ou possivelmente até mais do que um único exemplo, porque não vejo que tipo de limitações isso coloca em um idioma. (Deve ser não regular? Livre de contexto? Ou nem mesmo em ? E etc.)$R$

Um exemplo será .$L = \{ x\ \ |\ \ binary(x) < binary(x^R), x\in [0,1]^*\}$

E ainda outro exemplo .$L' = \{ x\ \ |\ \ binary(x) > binary(x^R), x\in [0,1]^*\}$

A idéia é que, se você estabelecer uma regra para escolher apenas um deles. Você precisa escolher a regra de modo que os palíndromos sejam rejeitados ( f ( x ) < f ( x R ) , para palíndromos você deve ter f ( x ) = f ( x R ) ). Você também pode alterar o alfabeto. alfabeto binário apenas para obter uma resposta rápida.$x \neq x^R$$f(x) < f(x^R)$$f(x)= f(x^R)$

e L ' acima não são regulares. E todalinguagemanti-palíndricaserá não regular e pode ser tão ruim quanto uma linguagem não RE. Exemplo de uma linguagem indecidível: L = { x | de tal modo que b i n a r y ( x ) < b i n a r y ( X R ) , se ambos x e x R ∉ Halt ou ambos x e x R ∈ Halt, caso contrário, se$L$$L'$$L=\{x\ \ |\ \ $$binary(x)<binary(x^R)$$x$$x^R$ $\not\in$$x$$x^R$ $\in$ Parar$x \in$$\}$

Klaus Draeger explicou no comentário abaixo que a linguagem anti-palindrômica dada no início da resposta é livre de contexto: $L=\{x0y1x^R\ |\ x,y\in\{0,1\}^*\}$

Sobre como gerar alguns exemplos:

Com base na resposta de @shreesh, podemos provar que toda linguagem anti-palíndromo deve ter a forma paraalgunspedidos estritos e totais < .

De fato, dado qualquer anti-palíndromo , podemos definir um < associado da seguinte maneira. Começamos com qualquer enumeração x 0 , x 1 , … de { 0 , 1 } ∗ , onde cada palavra ocorre exatamente uma vez. Em seguida, alteramos a enumeração: para cada par de não palíndromos x , x R , trocamos sua posição para fazer com que aquele que pertence a L apareça antes do outro. A nova enumeração induz uma ordem total < satisfatória ( ∗ ) .$L$$<$$x_0,x_1,\ldots$$\{0,1\}^*$$x,x^R$$L$$<$$(*)$

Como todo definido como ( ∗ ) é não palíndromo, é trivial, portanto ( ∗ ) é uma caracterização completa de idiomas não palíndromos.$L$$(*)$$(*)$

Dirigindo-se à pergunta original, agora sabemos que podemos obter vários exemplos de linguagens anti-palíndromo elaborando pedidos < . Também sabemos que, ao fazer isso, não estamos nos restringindo a uma subclasse de idiomas, perdendo generalidade.$L$$<$

Sobre a pergunta "esses idiomas podem ser regulares?":

Para provar que qualquer anti-palíndromo não é regular, assuma por contradição que é regular.$L$

1. Desde regularidade é preservada pela reversão , também é regular.$L^R$
2. Como a regularidade é preservada pela união, , que é o conjunto de todos os não-palíndromos, também é regular.$L \cup L^R$
3. Como a regularidade é preservada pelo complemento, o conjunto de todos os palíndromos é regular.

Da última afirmação, podemos derivar uma contradição bombeando. (Veja aqui, por exemplo, uma solução)

Para o que vale, aqui está uma gramática simples, livre de contexto, para uma linguagem anti-palindrômica:

(In fact, this is the anti-palindromic language proposed by @shreesh, using lexicographic comparison for the less-than operator.)