Satz NDKA erkennt w-w-reversed

Einfache Sprache

Der NDKA, der w-w-reversed erkennt, funktioniert folgender Maßen:

1. Wir beginnen im Zustand $q_0$. Solange wir in $q_0$ sind entscheiden wir uns nichtdeterministisch für eine von zwei Optionen:
2. Wir habe die Mitte noch nicht erreicht, also wir lesen weiter von $w$ ein. Wir lesen noch Symbole von $w$ ein und kellern auf den Speicher ein.
3. Wir haben die Mitte erreicht, also wir lesen jetzt Symbole von $w^R$ ein. Dazu wechseln wir von $q_0$ in $q_1$. Falls wir tatsächlich die Mitte erreicht haben, befindet sich jetzt in dem Kellerspeicher $w$, wobei der der Anfang von $w$ unten und das Ende von $w$ oben ist.
4. Im Zustand $q_1$ lesen wir ein Symbol von der Eingabe ein und kellern ein Symbol vom Speicher aus und vergleichen beide. Falls es nicht das gleich Symbol ist, verwerfe.
5. Falls der Keller leer ist, dann akzeptiere.

Def. Satz NDKA erkennt w-w-reversed

Der NDKA $\mathcal P$, der w-w-reversed durch Endzustand erkannt, wird wie folgt konstruiert

$$P = (\{q_0,q_1,q_2\}, \{0,1\},\{0,1,Z_0\},\delta,\{q_0\},\{Z_0\}, \{q_2\} )\;,$$

wobei $\delta$ folgende Transitionen erlaubt:

| Ausgangs-Zustand | Eingabe-Symbol | Keller-Symbol | Folge-Zustand | neues Keller-Symbol | | —————- | ————– | ————- | ————- | ——————- | | $q_0$ | $1$ | $Z_0$ | $q_0$ | $1Z_0$ | | $q_0$ | $0$ | $Z_0$ | $q_0$ | $0Z_0$ | | $q_0$ | $0$ | $0$ | $q_0$ | $00$ | | $q_0$ | $0$ | $1$ | $q_0$ | $01$ | | $q_0$ | $1$ | $0$ | $q_0$ | $10$ | | $q_0$ | $1$ | $1$ | $q_0$ | $11$ | | $q_0$ | $\varepsilon$ | $Z_0$ | $q_1$ | $Z_0$ | | $q_0$ | $\varepsilon$ | $0$ | $q_1$ | $0$ | | $q_0$ | $\varepsilon$ | $1$ | $q_1$ | $1$ | | $q_1$ | $0$ | $0$ | $q_1$ | $\varepsilon$ | | $q_1$ | $1$ | $1$ | $q_1$ | $\varepsilon$ | | $q_1$ | $\varepsilon$ | $Z_0$ | $q_2$ | $Z_0$ |

Graphisch ergibt sich folgender NDKA:

Beweis: Wir zeigen, dass $\mathcal P$ w-w-reversed durch Endzustand erkennt. Wir müssen zeigen, dass $\mathcal P$ eine Eingabe $x$ akzeptiert gdw. ein $w$ existiert so, dass $x=ww^R$.

“$\Leftarrow$”: Sei $w$ so, das $x = ww^R$. Dann erlaubt die Definition von $\mathcal P$ folgende akzeptierende Berechnung, bestehend aus Folgekonfigurationen:

Zuerst ließ $\mathcal P$ $w$ ein und kellert es umgekehrt ein. Es “errät” nichtdeterministisch das Ende von $w$ und geht in den nächsten Zustand. Dann wird die übrige Eingabe und der Kellerinhalt verglichen. Zum Schluss geht man in den akzeptierenden Zustand $q_2$, da Eingabe und Keller leer sind.

“$\Rightarrow$”: Die Idee ist, dass eine akzeptierende Berechnung folgende Eigenschaften haben muss: Um im (einzigen) Endzustand $q_2$ zu landen, müssen wir in $q_1$, mit $Z_0$ auf dem Kellerspeicher, sein. Außerdem muss müssen wir in $q_0$ starten und genau einmal nach $q_1$ wechseln. Es reicht also zu Zeigen, dass $(q_0,x,\alpha)\overset{*}\vdash(q_1,\varepsilon,\alpha)$. Durch Induktion über die Länge von $x$ werden wir zeigen, dass

IB: Sei $|x| = 0$. Dann muss $x =\varepsilon$. Dann existiert $w = \varepsilon$, denn $\varepsilon\varepsilon^R = \varepsilon\varepsilon = \varepsilon = x$.

IS: Sei $|x| > 0$. Dann existiert eine Zerlegung von $x$ in eine Liste von Eingabesmybolen $a_1,a_2,\ldots,a_n$ mit $n > 0$, also $x=a_1\ldots a_n$. Ausgehend von der Konfiguration $(q_0,x,\alpha)$ hat $\mathcal P$ zwei mögliche Optionen:

1. $(q_0,x,\alpha)\vdash(q_1,x,\alpha)$. Da $\mathcal P$ jetzt in $q_1$ ist, können nur noch Symbole ausgekellert werden. Aus den Transitionsfunktion können wir aber erkennen, dass mit jedem ausgekellerten Symbol auch ein Symbol von der Eingabe gelesen werden muss. Da die Eingabe länger ist als der Keller, würden mehr Symbole als $\alpha$ ausgekellert (siehe Induktionsbehauptung). Dieser Fall ist also keine erfolgreiche Berechnung.
2. $(q_0,a_1,a_2,\ldots,a_n,\alpha)\vdash(q_1,a_2,\ldots,a_n,a_1\alpha)$. Jetzt wissen wir, dass wir $(q_1,\varepsilon, \alpha)$ nur erreichen können, wenn $$(q_1,a_n,a_1\alpha)\vdash(q_1,\varepsilon, \alpha)\;.$$ Es muss also $a_1 = a_n$ gelten. Wir wissen auch, dass $$(q_0,a_2\ldots a_n,a_1\alpha)\overset{*}\vdash(q_1,a_n, a_1\alpha)\;.$$ Jetzt können wir nach dem Satz ungelesene Eingabe und unbenutzer Speicher beeinflusst Erweiterte Folgekonfiguration nicht $a_n$ von dem Ende der Eingabe entfernen und erhalten $$(q_0,a_2\ldots a_{n-1},a_1\alpha)\overset{*}\vdash(q_1,\varepsilon, a_1\alpha)\;.$$ Die übrige Eingabe $v = a_2\ldots a_{n-1}$ ist kürzer als $n$. Wir wenden die IH an und folgen dein ein $y\in A^*$ so existiert, dass $v = yy^R$. Da $x = a_1yy^Ra_n$ und $x_1 = x_n$, folgt das $x =ww^R$ für $w=a_1y$.