Znalezienie przykładów języków „antypalindromicznych”

Niech $\Sigma = \{ 0, 1 \}$ . Język mówi się, że „anty-palindrom” własność jeśli każdy ciąg że jest palindrom, . Ponadto dla każdego łańcucha który nie jest palindromem, lub , ale nie oba (!) (Wyłączne lub).$L \subseteq \Sigma^*$$w$$w\notin L$$u$$u\in L$$\mathrm{Reverse}(u) \in L$

Rozumiem właściwość anty-palindromową, ale nie mogłem znaleźć języków, które mają tę właściwość. Najbliższy jeden udało mi się znaleźć to , ale nie posiada wyłączne lub część ... to jest, na przykład, zarówno i są w .$\Sigma^* \setminus L$$01$$10$$L$

Czy ktoś mógłby mi podać przykład języka, który ma tę właściwość? A może nawet więcej niż jeden przykład, ponieważ nie widzę, jakie ograniczenia to nakłada na język. (Czy musi to być nieregularny? Bez kontekstu? Lub nawet w ? I itp.)$R$

Jednym z przykładów będzie .$L = \{ x\ \ |\ \ binary(x) < binary(x^R), x\in [0,1]^*\}$

I jeszcze inny przykład .$L' = \{ x\ \ |\ \ binary(x) > binary(x^R), x\in [0,1]^*\}$

Chodzi o to, że jeśli ustalasz regułę, aby wybrać tylko jeden z nich. Musisz wybrać regułę, aby palindromy były odrzucane ( f ( x ) < f ( x R ) , dla palindromów musisz mieć f ( x ) = f ( x R ) ). Możesz także zmienić alfabet, wziąłem alfabet binarny, aby uzyskać szybką odpowiedź.$x \neq x^R$$f(x) < f(x^R)$$f(x)= f(x^R)$

i L ′ powyżej nie są regularne. I każdyjęzykanty-palindromicznybędzie nieregularny i może być tak samo zły jak język inny niż RE. Egzamin z nierozstrzygalnego języka: L = { x | taki, że b i n a r y ( x ) < b i n a r y ( x R ), jeśli zarówno x i x R ∉ Zatrzymaj lub zarówno x i x R ∈ Zatrzymaj, w przeciwnym razie, jeżeli$L$$L'$$L=\{x\ \ |\ \ $$binary(x)<binary(x^R)$$x$$x^R$ $\not\in$$x$$x^R$ $\in$ Zatrzymaj$x \in$$\}$

Klaus Draeger wyjaśnił w komentarzu poniżej, że język anty-palindromiczny podany na początku odpowiedzi jest pozbawiony kontekstu: $L=\{x0y1x^R\ |\ x,y\in\{0,1\}^*\}$

About generating a few examples:

Building on the answer of @shreesh, we can prove that every anti-palindrome language must be of the form

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 $(*)$.

To, że każde zdefiniowane jako ( ∗ ) nie jest palindromem, jest banalne, więc ( ∗ ) jest pełną charakterystyką języków innych niż palindrom.$L$$(*)$$(*)$

Odpowiadając na pierwotne pytanie, wiemy teraz, że możemy uzyskać kilka przykładów języków anty-palindromowych , tworząc zamówienia < . Wiemy również, że robiąc to, nie ograniczamy się do podklasy języków, tracąc ogólność.$L$$<$

O pytaniu „czy te języki mogą być regularne?”:

Aby udowodnić, że jakikolwiek anty-palindrom nie jest regularny, załóż przez sprzeczność, że jest on regularny.$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.)