Encontrar ejemplos de lenguajes que son "antipalindrómicos"

Deje $\Sigma = \{ 0, 1 \}$ . Un lenguaje $L \subseteq \Sigma^*$ se dice que tiene la propiedad "anti-palíndromo" si para cada cadena $w$ que es un palíndromo, $w\notin L$ . Además, para cada cadena que no es un palíndromo, o , pero no ambos (!) (Exclusivo o).u ∈ L R e v e r s e ( u $u$$u\in L$$\mathrm{Reverse}(u) \in L$

Entiendo la propiedad anti-palíndromo, pero no pude encontrar ningún idioma que tenga esta propiedad. El más cercano que pude encontrar es , pero no tiene la exclusiva o parte ... que es, por ejemplo, ambos y están en .01 $\Sigma^* \setminus L$$01$$10$$L$

¿Alguien podría darme un ejemplo de un idioma que tenga esta propiedad? O posiblemente incluso más que un solo ejemplo, porque no veo qué tipo de limitaciones pone esto en un idioma. (¿Debe ser no regular? ¿Sin contexto? ¿O ni siquiera en ? Y etc.)$R$

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

Y otro ejemplo más .$L' = \{ x\ \ |\ \ binary(x) > binary(x^R), x\in [0,1]^*\}$

La idea es que si haces una regla para elegir solo uno de ellos. Debe elegir la regla para que los palíndromos se rechacen ( f ( x ) < f ( x R ) , para los palíndromos debe tener f ( x ) = f ( x R ) ). También puede cambiar el alfabeto, tomé alfabeto binario solo para obtener una respuesta rápida.$x \neq x^R$$f(x) < f(x^R)$$f(x)= f(x^R)$

y L ' anteriores no son regulares. Y cadalenguajeantipalindrómicoserá no regular y puede ser tan malo como un lenguaje que no sea RE. Ejemplo de un lenguaje indecidible: L = { x | tal que b i n a r y ( x ) < b i n a r y ( x R ) si tanto x como x R ∉ Detener o ambas x y x R ∈ Detener, de lo contrario si$L$$L'$$L=\{x\ \ |\ \ $$binary(x)<binary(x^R)$$x$$x^R$ $\not\in$$x$$x^R$ $\in$ Alto$x \in$$\}$

Klaus Draeger explicó en el comentario a continuación que el lenguaje antipalindrómico dado al comienzo de la respuesta no tiene contexto: $L=\{x0y1x^R\ |\ x,y\in\{0,1\}^*\}$

Acerca de generar algunos ejemplos:

Sobre la base de la respuesta de @shreesh, podemos demostrar que cada lenguaje antipandrome debe ser de la forma paraalgunospedidos totales estrictos < .

Indeed, given any anti-palindrome $L$, we can define an associated $<$ as follows. We start by taking any enumeration $x_0,x_1,\ldots$ of $\{0,1\}^*$, where each word occurs exactly once. Then, we alter the enumeration: for each pair of non-palindromes $x,x^R$, we swap their position so to make the one that belongs to $L$ to appear before the other. The new enumeration induces a total ordering $<$ satisfying $(*)$.

Que cada definida como ( ∗ ) sea ​​no palíndromo es trivial, por lo que ( ∗ ) es una caracterización completa de lenguajes no palíndromos.$L$$(*)$$(*)$

Al abordar la pregunta original, ahora sabemos que podemos obtener varios ejemplos de lenguajes anti-palíndromo elaborando pedidos < . También sabemos que al hacerlo no nos estamos restringiendo a una subclase de idiomas, perdiendo generalidad.$L$$<$

Sobre la pregunta "¿pueden estos idiomas ser regulares?":

Para probar que cualquier antipalíndromo no es regular, suponga por contradicción que es regular.$L$

1. Since regularity is preserved by reversal, $L^R$ is also regular.
2. Since regularity is preserved by union, $L \cup L^R$, which is the set of all the non-palindromes, is also regular.
3. Since regularity is preserved by complement, the set of all palindromes is regular.

From the last statement, we can derive a contradiction by pumping. (See e.g. here for a solution)

For what it's worth, here is a simple context-free grammar for one anti-palindromic language:

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