Beispiele für Sprachen finden, die „antipalindromisch“ sind

Es sei . Eine Sprache gesagt wird die „anti-Palindrom“ Eigenschaft hat , wenn für jede Saite dass ein Palindrom ist, . Außerdem ist für jede Zeichenfolge , die kein Palindrom ist, entweder oder , aber nicht beide (!) (Exklusive oder). $\Sigma = \{ 0, 1 \}$ $L \subseteq \Sigma^*$ $w$ $w\notin L$ $u$ $u\in L$ $\mathrm{Reverse}(u) \in L$

Ich verstehe die Anti-Palindrom-Eigenschaft, konnte jedoch keine Sprachen finden, die diese Eigenschaft aufweisen. Die nächstgelegene ich finden konnte , ist , aber es hat nicht die ausschließliche oder teil ... das heißt, beispielsweise sowohl und sind in . $\Sigma^* \setminus L$ $01$ $10$ $L$

Könnte mir jemand ein Beispiel für eine Sprache geben, die diese Eigenschaft hat? Oder vielleicht sogar mehr als ein einzelnes Beispiel, weil ich nicht verstehe, welche Einschränkungen dies für eine Sprache mit sich bringt. (Muss es nicht regelmäßig sein? Kontextfrei? Oder nicht einmal in ? Und etc.) $R$

formal-languages Marik S.
quelle

"Ich konnte keine Sprachen finden, die diese Eigenschaft haben." - Sie haben gerade eine durch Angabe der Eigenschaft definiert, vorausgesetzt, es gibt eine Sprache, die die Bedingung erfüllt.

Raphael

Ich stimme nicht zu, was er definierte, war eine Klasse von Sprachen. Das ist keine genau definierte Definition für eine Sprache.

Shreesh

Antworten:

Ein Beispiel ist . $L = \{ x\ \ |\ \ binary(x) < binary(x^R), x\in [0,1]^*\}$

Und noch ein Beispiel . $L' = \{ x\ \ |\ \ binary(x) > binary(x^R), x\in [0,1]^*\}$

Die Idee ist, wenn Sie eine Regel bilden, um nur einen von ihnen zu wählen. Sie müssen die Regel so wählen, dass Palindrome verworfen werden sollen ( , für Palindrome müssen Sie ) haben. Sie können auch das Alphabet ändern, Ich habe binäres Alphabet genommen, um eine schnelle Antwort zu bekommen. $x \neq x^R$ $f(x) < f(x^R)$ $f(x)= f(x^R)$

$L$ und sind nicht regelmäßig. Und jede antipalindromische Sprache ist nicht regelmäßig und kann genauso schlecht sein wie eine Sprache ohne RE. Ein Beispiel für eine unentscheidbare Sprache: so dass wenn sowohl als auch Halt oder sowohl als auch Halt, sonst wenn Halt $L'$ $L=\{x\ \ |\ \$ $binary(x)<binary(x^R)$ $x$ $x^R$ $\not\in$ $x$ $x^R$ $\in$ $x \in$ $\}$

Klaus Draeger erklärte im Kommentar unterhalb dieser anti-Palindrom Sprache am Anfang der Antwort ist kontextfrei: $L=\{x0y1x^R\ |\ x,y\in\{0,1\}^*\}$

Shreesh
quelle

Ich verstehe, also ist es wahr, dass jede Anti-Palindrom-Sprache nicht regelmäßig ist. Aber kann man sagen, dass es in ? denn selbst wenn wir diese Idee erweitern, kann jede Reihenfolge / Funktion, die wir verwenden, mit einem TM in ..right berechnet werden?

R

$R$

R

$R$

Marik S.

@Marik Es gibt gut definierte, aber nicht berechenbare Funktionen . Zum Beispiel Mapping von Zahlen, die M, w in Halting Problem darstellen, auf [0,1].

Shreesh

Ja, aber können solche Funktionen eine Gesamtreihenfolge für ?

Σ^{*}

$\Sigma^*$

Marik S.

Ja. Zum Beispiel wenn sowohl als auch oder Halt sind, andernfalls oder je nachdem, was in Halt ist . Halt ist alles so, dass auf .

L = {x | x \neq x^{R}, b i n a r y (x) < b i n a r y (x^{R})

$L = \{x | x \neq x^R, binary(x) < binary(x^R)$

x

$x$

x^{R} \notin

$x^R \not\in$

\in

$\in$

x

$x$

x^{R}

$x^R$

}

$\}$

(M, w)

$(M,w )$

M

$M$

w

$w$

Shreesh

Und wenn Sie eine Diagonalisierungssprache verwenden, wird diese zu einer Non-RE-Sprache.

Shreesh

Über das Generieren einiger Beispiele:

Aufbauend auf der Antwort von @shreesh, können wir beweisen , dass jede anti-Palindrom Sprache der Form sein muss für einige strenge totale Ordnung .

L = {x | x < x^{R}} (*)

$L = \{ x \ |\ x < x^R \}\qquad (*)$

<

$<$

In der Tat können wir bei jedem Anti-Palindrom ein assoziiertes wie folgt definieren. Wir beginnen mit einer beliebigen Aufzählung von , wobei jedes Wort genau einmal vorkommt. Dann ändern wir die Aufzählung: Für jedes Paar von Nicht-Palindromen tauschen wir ihre Position, damit dasjenige, das zu gehört, vor dem anderen erscheint. Die neue Aufzählung führt zu einer Gesamtreihenfolge befriedigend . $L$ $<$ $x_0,x_1,\ldots$ $\{0,1\}^*$ $x,x^R$ $L$ $<$ $(*)$

Daß jedes als definierte kein Palindrom ist, ist trivial, so daß eine vollständige Charakterisierung von nicht-palindromen Sprachen ist. $L$ $(*)$ $(*)$

Wenn wir uns der ursprünglichen Frage widmen, wissen wir jetzt, dass wir mehrere Beispiele für Anti-Palindrom-Sprachen erhalten können, indem wir Bestellungen . Wir wissen auch, dass wir uns dadurch nicht auf eine Unterklasse von Sprachen beschränken, sondern die Allgemeinheit verlieren. $L$ $<$

Über die Frage "Können diese Sprachen regelmäßig sein?":

Um zu beweisen, dass ein Anti-Palindrom nicht regelmäßig ist, wird im Widerspruch angenommen, dass es regelmäßig ist. $L$

Da die Regelmäßigkeit durch Umkehrung erhalten bleibt , ist auch regelmäßig. $L^R$
Da die Regelmäßigkeit durch Vereinigung erhalten bleibt, ist auch , die Menge aller Nicht-Palindrome, regelmäßig. $L \cup L^R$
Da die Regelmäßigkeit durch Ergänzung erhalten bleibt, ist die Menge aller Palindrome regelmäßig.

Aus der letzten Aussage können wir durch Pumpen einen Widerspruch ableiten. (Siehe zB hier für eine Lösung)

chi
quelle

Oder einfacher gesagt: Damit ein DFA die Sprache der Palindrome akzeptiert, muss er beim Parsen der zweiten Hälfte die erste Hälfte der Zeichenfolge berücksichtigen. Ein DFA hat jedoch eine endliche Anzahl von Zuständen und kann keine speichern beliebig lange Saite. Dieselbe Überlegung zeigt, dass die Sprache der ausgeglichenen Klammern nicht regelmäßig ist (die Parentiefe kann beliebig groß sein).

Kevin

Ich sehe, aber wenn irgendein diese Eigenschaft hat, dann aus der Form bedeutet dies, dass jede Sprache auch kontextfrei ist? Oder wenn nicht CFL, muss es in ? da jeder Auftrag mit einem TM in berechnet werden kann .

L

$L$

L = {x | x < x^{R}}

$L=\{ x | x<x^R \}$

R

$R$

<

$<$

R

$R$

Marik S.

@MarikS. Die folgende Grammatik von rici beweist, dass kontextfrei sein kann. Ich bin mir ziemlich sicher, dass einige nicht rekursiv sind, da es unzählige solcher Sprachen gibt - in meinem Beweis oben können wir unzählige Entscheidungen treffen, welche als erstes zwischen und , und jede Kombination gibt eine andere . Die Kardinalität solcher Sprachen ist also die gleiche wie bei , was unzählig ist.

L

$L$

L

$L$

x

$x$

x^{R}

$x^R$

L

$L$

{0, 1}^{N}

$\{0,1\}^{\mathbb{N}}$

Chi

Hier ist eine einfache kontextfreie Grammatik für eine antipalindromische Sprache:

\begin{aligned} S & \to 0 S 0 ∣ 1 S 1 ∣ 0 X 1 \\ X & \to ϵ ∣ X 0 ∣ X 1 \end{aligned}

$\begin{align} S &\to 0 S 0 \mid 1 S 1 \mid 0 X 1 \\ X &\to \epsilon \mid X 0 \mid X 1 \end{align}$

(Tatsächlich handelt es sich hierbei um die von @shreesh vorgeschlagene antipalindromische Sprache, bei der ein lexikografischer Vergleich für den Kleiner-als-Operator verwendet wird.)

rici
quelle

Was zu einer noch genaueren Beschreibung führt: .

L = {x 0 y 1 x^{R} | x, y \in {0, 1}^{*}}

$L=\{x0y1x^R\ |\ x,y\in\{0,1\}^*\}$

Klaus Draeger