Trouver des exemples de langues «anti-palindromiques»

Soit $\Sigma = \{ 0, 1 \}$ . Un langage $L \subseteq \Sigma^*$ est dit d'avoir la propriété « anti-palindrome » si pour chaque chaîne $w$ qui est un palindrome, $w\notin L$ . De plus, pour chaque chaîne $u$ qui n'est pas un palindrome, soit $u\in L$ ou $\mathrm{Reverse}(u) \in L$ , mais pas les deux (!) (Exclusif ou).

Je comprends la propriété anti-palindrome, mais je n'ai trouvé aucune langue possédant cette propriété. Le plus proche que je pouvais trouver est $\Sigma^* \setminus L$ , mais il n'a pas l'exclusivité ou d'une partie ... qui est, par exemple, les $01$ et $10$ sont en $L$ .

Quelqu'un pourrait-il me donner un exemple d'une langue qui a cette propriété? Ou peut-être même plus qu'un seul exemple, car je ne vois pas quel genre de limitations cela met sur une langue. (Doit-il être non régulier? Sans contexte? Ou même pas en $R$ ? Et etc.)

Un exemple sera .$L = \{ x\ \ |\ \ binary(x) < binary(x^R), x\in [0,1]^*\}$

Et encore un autre exemple .$L' = \{ x\ \ |\ \ binary(x) > binary(x^R), x\in [0,1]^*\}$

L'idée est que si vous faites une règle pour n'en choisir qu'un seul. Vous devez choisir la règle pour que les palindromes soient rejetés ( f ( x ) < f ( x R ) , pour les palindromes, vous devez avoir f ( x ) = f ( x R ) ) .Vous pouvez également changer l'alphabet, j'ai pris alphabet binaire juste pour obtenir une réponse rapide.$x \neq x^R$$f(x) < f(x^R)$$f(x)= f(x^R)$

et L ' ci-dessus ne sont pas réguliers. Et chaquelangueanti-palindromiquesera non régulière et peut être aussi mauvaise qu'une langue non RE. Exemple d'une langue indécidable: L = { x | tel que b i n a r y ( x ) < b i n a r y ( x R ) si x et x R ∉ Halt ou x et x R ∈ Halt, sinon si$L$$L'$$L=\{x\ \ |\ \ $$binary(x)<binary(x^R)$$x$$x^R$ $\not\in$$x$$x^R$ $\in$ Arrêter$x \in$$\}$

Klaus Draeger a expliqué dans le commentaire ci-dessous que le langage anti-palindromique donné au début de la réponse est hors contexte: $L=\{x0y1x^R\ |\ x,y\in\{0,1\}^*\}$

À propos de la génération de quelques exemples:

En nous appuyant sur la réponse de @shreesh, nous pouvons prouver que chaque langage anti-palindrome doit être de la forme pourcertainescommandes totales strictes < .

En effet, compte tenu de tout anti-palindrome , on peut définir un < associé comme suit. Nous commençons par prendre n'importe quelle énumération x 0 , x 1 , … de { 0 , 1 } ∗ , où chaque mot apparaît exactement une fois. Ensuite, nous modifions l'énumération: pour chaque paire de non-palindromes x , x R , nous échangeons leur position afin de faire apparaître celle qui appartient à L avant l'autre. La nouvelle énumération induit un ordre total < satisfaisant ( ∗ ) .$L$$<$$x_0,x_1,\ldots$$\{0,1\}^*$$x,x^R$$L$$<$$(*)$

Que chaque défini comme ( ∗ ) est non palindrome est trivial, donc ( ∗ ) est une caractérisation complète des langages non palindromes.$L$$(*)$$(*)$

En répondant à la question initiale, nous savons maintenant que nous pouvons obtenir plusieurs exemples de langages anti-palindromes en créant des ordonnances < . Nous savons également qu'en faisant cela, nous ne nous limitons pas à une sous-classe de langues, en perdant la généralité.$L$$<$

A propos de la question "ces langues peuvent-elles être régulières?":

Pour prouver que tout anti-palindrome n'est pas régulier, supposons par contradiction qu'il est régulier.$L$

1. La régularité étant préservée par retournement , est également régulière.$L^R$
2. La régularité étant préservée par l'union, , qui est l'ensemble de tous les non-palindromes, est également régulier.$L \cup L^R$
3. La régularité étant préservée par le complément, l'ensemble de tous les palindromes est régulier.

De la dernière déclaration, nous pouvons tirer une contradiction en pompant. (Voir par exemple ici pour une solution)

Pour ce que ça vaut, voici une grammaire simple sans contexte pour un langage anti-palindromique:

(En fait, c'est le langage anti-palindromique proposé par @shreesh, utilisant la comparaison lexicographique pour l'opérateur inférieur à.)