cards-deck: date created: Wednesday, February 21st 2024, 12:07:36 am date modified: Tuesday, May 7th 2024, 1:32:21 pm date-created: 2024-02-21 12:07:36 date-modified: 2024-09-26 08:49:46

| Kellerautomaten | PDA

anchored to 112.00_anchor_overview

requires 112.02_deterministische_automaten

Wir haben zuvor bereits herausgefunden, dass endliche Automaten meist ziemlich beschränkt sind, denn sie haben beschränkten Speicher (bzw. keinen) und können diverse Sprachen, die beispielsweise das Zählen voraussetzen würden, nicht erkennen. Als Beispiel gilt: $L=\{a^n{b}^n|n\in \mathbb{N}\}$ Da wir zwar theoretisch einen Sprung von a,b gestalten könnten, aber beispielsweise nicht zählen, wie oft wir etwas durchlaufen sind. Um dieses Problem etwas eliminieren zu können, benötigen wir etwas mit Speicher.

Here comes the Kellerautomat, welcher einen Stack als Speicher implementiert.

Intuition eines Kellerautomaten

Betrachten wir einen endlichen Automaten, der zusätzlich noch einen Stack im Keller hat. Stack beschreibt hier die Datenstruktur im LIFO Prinzip.

Wir haben also einen Stack erzeugt, den wir betrachten, beschreiben und löschen könne. Dadurch wird es uns ermöglicht ,dass wir auf Daten, die wir lesen, zugreifen und sie eventuell speichern können. Da es sich nur um einen Stack handelt, können wir hier ferner also nur begrenzt Daten speichern und sinnig abrufen. –> halt nur chronologisch obv.

Würde man vermuten, dass dieser mehr kann, als ein endlicher Automat?

Die Sprache ($L=\{a^n{b}^n|n\in \mathbb{N}\}$), also die n-malige Wiederholung von zwei beliebigen Werten a und b, sollte er schonmal erkennen und akzeptieren können. Warum ? :: Denn ihm obliegt es die Quantität von $a$ im Stack zu zählen bzw für jedes auftretendes $b$ ein $a$ vom stack nehmen und so akzeptieren, wenn der Stack am Ende leer ist.

Definition eines Kellerautomaten:

[!Definition] Kellerautomaten (PDA)

Ein nicht deterministischer Kellerautomat besteht aus einem 6-Tupel $(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$ wobei folgende Bezeichnungen gelten: #card

• $Q$ ist eine endliche Zustandsmenge des Automaten
• $\Sigma$ ein Eingabealphabet
• $\Gamma$ das Stack-Alphabet
• $q_0$ der Startzustand, wobei $q_0\in Q$ Ferner ist bei $q_0$ auch $s_0=\epsilon$, also der Stack startet mit leerer Eingabe.
• $F\subset Q$ ist die Menge der akzeptierenden Zustände
• und die Übergangsfunktion $\delta$ mit $\delta :Q\times (\Sigma \cup \{ϵ\})\times (\Gamma \cup \{ϵ\})⟹\mathbf{P}(Q\times (\Gamma \cup \{ϵ\}))$ definiert ist.

Wir haben keinen Anspruch, dass das Kelleralphabet größer / oder disjunkt zum Eingabealphabet ist (oder nicht). Es kann hierbei also mächtiger sein oder aber geringerwertiger Meist hat es mehr, weil man damit bestimmte Markierungen, wie # , beschreiben / einfügen kann, die wichtig sind, wenn man angeben, möchte, wo der Stack anfängt.

[!Attention] Nichtdeterminismus $\ne$ Determinismus warum? #card Ferner sagen wir aus, dass wir hier Nichtdeterminismus verwenden wollen. Für einen PDA - Kellerautomaten! - gilt im Allgemeinen nicht, dass die deterministische / nichtdeterministische Formen die gleich Sprache akzeptieren kann.

Die Übergangsfunktion eines Kellerautomaten ist in seiner Struktur nun etwas anders / brauch noch einen weiteren Zustand:

[!Tip] Übergangsfunktion des Automaten

$$\delta :Q\times (\Sigma \cup \{ϵ\})\times (\Gamma \cup \{ϵ\})⟹\mathbf{P}(Q\times (\Gamma \cup \{ϵ\}))$$

Was beschreibt sie bzw was sind ihre Eigenschaften? #card

Wir beschreiben folgend die Übergangsfunktion als Konkatenation des Kelleralphabets, des EIngabealpahbets und der Zustände –> Es sind also drei Faktoren, die bestimmen, wie unser Automat sich verhalten wird / muss / kann

potentielle Ausführung Der Automat ist in einem Zustand $Q$, liest eventuell (dafür steht $ϵ$) einen Buchstaben vom Eingabewort ($\Sigma \dots$) und holt eventuell (dafür auch $ϵ$) einen Buchstaben vom Stack $\Gamma \dots$ . Danach geht er in einen neuen Zustand und schreibt eventuell einen Buchstaben auf den Stack/

Wir betrachten hier die Potenzmenge, weil dieser Ablauf nicht zwingend deterministisch sein muss!

[!Attention] Typ 3 Sprachen in Kellerautomaten - und deren Sprachbereich - enthalten warum? #card

Betrachten wir einen Kellerautomat, der seinen Stack nicht verwendet und somit immer leer lässt und nicht einbezieht, ist quasi äquivalent zu einem DFA / NFA und kann somit alles darstellen, was ein normaler DFA auch kann

–> sie deckt also alle Regulären Sprachen ab!

Beispiel | Kellerautomat

Sprache | $0^n{1}^n\mid n\ge 0$

Betrachten wir folgenden Kellerautomaten, dargestellt aus Automat: Wir beschreiben ihn folgend: $$L=\{0^n{1}^n\mid n\ge 0\}\notin REG$$ Beschreiben wir sie als Automat können wir die folgenden Parameter beschreiben:

$$\begin{array}{rl}Q& =\{q_1,q_2,q_3,q_4\}\\ \Sigma & =\{0,1\}\\ \Gamma & =\{0,\#\}\\ F& =\{q_1,q_4\}\\ \delta & =\text{ definiert wie in der Tabelle}\end{array}$$

\usepackage{tikz}

\begin{document}

\begin{tikzpicture}[scale=0.3]
\tikzstyle{every node}+=[inner sep=0pt]
\draw [black] (17.9,-9) circle (3);
\draw (17.9,-9) node {$q1$};
\draw [black] (17.9,-9) circle (2.4);
\draw [black] (37.5,-9) circle (3);
\draw (37.5,-9) node {$q2$};
\draw [black] (37.5,-28.7) circle (3);
\draw (37.5,-28.7) node {$q3$};
\draw [black] (17.9,-28.7) circle (3);
\draw (17.9,-28.7) node {$q4$};
\draw [black] (17.9,-28.7) circle (2.4);
\draw [black] (7.3,-9) -- (14.9,-9);
\draw (6.8,-9) node [left] {$start$};
\fill [black] (14.9,-9) -- (14.1,-8.5) -- (14.1,-9.5);
\draw [black] (20.9,-9) -- (34.5,-9);
\fill [black] (34.5,-9) -- (33.7,-8.5) -- (33.7,-9.5);
\draw (27.7,-9.5) node [below] {$eps,\mbox{ }eps->\mbox{ }hash$};
\draw [black] (40.481,-8.791) arc (121.75098:-166.24902:2.25);
\draw (44.49,-12.46) node [right] {$0,\mbox{ }eps->hash$};
\fill [black] (39.48,-11.24) -- (39.48,-12.18) -- (40.33,-11.66);
\draw [black] (37.5,-12) -- (37.5,-25.7);
\fill [black] (37.5,-25.7) -- (38,-24.9) -- (37,-24.9);
\draw (37,-18.85) node [left] {$1,0->eps$};
\draw [black] (39.947,-26.985) arc (152.74616:-135.25384:2.25);
\draw (44.87,-27.48) node [right] {$1,0->\mbox{ }eps$};
\fill [black] (40.35,-29.6) -- (40.83,-30.41) -- (41.29,-29.52);
\draw [black] (34.5,-28.7) -- (20.9,-28.7);
\fill [black] (20.9,-28.7) -- (21.7,-29.2) -- (21.7,-28.2);
\draw (27.7,-28.2) node [above] {$eps,\mbox{ }hash\mbox{ }->\mbox{ }eps$};
\end{tikzpicture}

\end{document}

Wir betrachten hier im Übergang immer zwei Werte, wobei der erste dem Input zugewiesen wird und der zweite Input vom Stack kommt.

Wir bezeichnen hier ferner hash “#” als ein End-Symbol, was angibt, dass der Stack wieder Leer ist, bzw. dass wir angeben, dass unser Stack “jetzt leer ist, wir also keine Ein/Ausgabe für diesen mehr annehmen sollten/wollen”. -> Unser Automat geht deswegen in den akzeptierenden Zustand über, wenn der Stack leer ist und wir somit die gleiche Menge von 0 und 1 geschrieben haben!

Als Übergangstabelle können wir es folgend darstellen:

Dyck-Sprache | $\{w\in \{(,){\}}^{\ast }\}$

Betrachten wir ferner nochmal die Dyck-Sprache, die beliebig viele Klammern - verschiedenster Art - akzeptiert, wenn sie genau matchen.

Wir wollen mit dem Kellerautomat immer speichern, was gerade eingebracht wurde und anschließend noch, wann dieser Part wieder geschlossen wird. Das heißt der Stack enthält immer das zuletzt geöffnete Symbol, welches wir anschließend wieder schließen müssen. Passiert das nicht, akzeptiert der Automat auch nicht!

Wir wollen hierbei immer zuerst den Terminal $\#$ eintragen, der das Ende des Stacks darstellt und ferner setzen wir immer eine Klammer auf den Stack-wenn eine existiert, und sofern eine Klammer schließt, entfernen wir sie wieder vom Stack. Also Automat sieht es folgend aus:

\usepackage{tikz}
\begin{document}

\begin{tikzpicture}[scale=0.2]
\tikzstyle{every node}+=[inner sep=0pt]
\draw [black] (25.7,-11.8) circle (3);
\draw (25.7,-11.8) node {$q1$};
\draw [black] (35.1,-25.7) circle (3);
\draw (35.1,-25.7) node {$q2$};
\draw [black] (25.7,-39.7) circle (3);
\draw (25.7,-39.7) node {$q3$};
\draw [black] (27.38,-14.29) -- (33.42,-23.21);
\fill [black] (33.42,-23.21) -- (33.39,-22.27) -- (32.56,-22.83);
\draw (29.79,-20.09) node [left] {$eps,esp\mbox{ }->\#$};
\draw [black] (36.366,-22.993) arc (182.65981:-105.34019:2.25);
\draw (40.93,-20.06) node [right] {$(,\mbox{ }eps->\mbox{ }($};
\fill [black] (38.02,-25.06) -- (38.84,-25.52) -- (38.79,-24.52);
\draw [black] (37.841,-26.891) arc (94.23636:-193.76364:2.25);
\draw (45.51,-31.35) node [below] {$),(->\mbox{ }eps$};
\fill [black] (35.82,-28.6) -- (35.38,-29.43) -- (36.38,-29.36);
\draw [black] (14.4,-11.8) -- (22.7,-11.8);
\draw (13.9,-11.8) node [left] {$start$};
\fill [black] (22.7,-11.8) -- (21.9,-11.3) -- (21.9,-12.3);
\draw [black] (33.43,-28.19) -- (27.37,-37.21);
\fill [black] (27.37,-37.21) -- (28.23,-36.82) -- (27.4,-36.27);
\draw (29.79,-31.36) node [left] {$eps,\#->\mbox{ }eps$};
\end{tikzpicture}

\end{document}

Beispiel | $w{w}^R\mid w\text{ u¨ber }\Sigma$

$L=\{w{w}^R|w\text{ Wort u¨ber}\Sigma \}$ ist eine Sprache, die vom Kellerautomaten erkannt werden kann. Hierbei wird $w^R$ als das Wort, aber rückwärts, definiert. warum ist diese Struktur möglich? #card Diese Struktur ist möglich, weil wir nach jeder Eingabe schauen können, ob der Buchstabe schon im Stack auftaucht oder nicht. Sofern er schon auftritt - wir gehen jetzt davon aus, dass ein Wort keine wiederholenden Buchstaben hat! - dann wissen wir, dass das Wort vorbei und jetzt das gleich rückwärts kommt. Ab jetzt können wir also immer gegen checken, ob unser Wort auch im Stack vorhanden ist und es dann daraus entfernen und am Ende muss auch hier der Stack wieder leer sein. Mit dem Fall, dass Wörter auch mehrere Buchstaben enthalten, kann man den Automaten dann als nichtdeterministischen laufen lassen, welcher alle Möglichkeiten abläuft und verarbeitet. ^1686044663015

Ein weiteres Beispiel: $L=\{a^n{b}^n|n\in \mathbb{N}\}$ weswegen kann diese Sprache erkannt werden? #card Wie am Anfang betrachtet, kann man hier einfach X lange zählen, indem man den Buchstaben $a$ in den Stack aufnimmt, und nach Abschluss des Auftretens für jedes $b$ ein $a$ aus dem Stack entfernen. Am Ende muss dieser wieder leer sein, dann wurde die Sprache gefunden.

Gegenbeispiele

$L=\{ww|w\text{ Wort in}\Sigma \}$ weswegen kann diese Sprache nicht erkannt werden? #card Das ist nicht möglich, weil der Automat nicht erkennen kann, wann das erste Wort zuende und das nächste begonnen hat. Bei $w{w}^R$ war es möglich, weil wir die Elemente anschließend gut miteinander vergleichen konnten –> Stacks arbeiten nach LIFO!, also invertieren ein Wort automatisch.

$L=\{a^n{b}^n{c}^n\}$ weswegen ist diese Sprache nicht erkennbar mit dem Kellerautomaten? #card Zuvor haben wir $a^n{b}^n$ bewiesen, aber würden wir für diese Sprache schon den Teil $a^n{b}^n$ bearbeiten, dann wäre der Stack danach leer und wir könnten nicht mehr schauen, ob $c^n$die gleiche Anzahl hat. Generell würde auch die Sprache: $a^n{b}^n{c}^n{d}^n$ nicht möglich sein, weil wir nach entleeren des Stacks keine Informationen über $a,b$ haben und somit nicht mehr vergleichen und somit überprüfen können.

(Theorem) | Kellerautomaten $⟺$ Kontextfreie Grammatiken

Wir wollen jetzt also zeigen, dass die Konstruktion eines Kellerautomaten helfen kann, dass wir damit eine kontextfreie Sprache darstellen können.

Ferner heißt das jetzt:

[!Proposition]

Eine Sprache ist kontextfrei genau dann :: wenn es einen Kellerautomaten gibt, der sie erkennt.

Diese Aussage möchten wir jetzt beidseitig beweisen. Dafür betrachten wir eine kontextfreie Sprache, welche auf einer kontextfreien Grammatik basiert. Anschließend werden wir in der Lage sein einen PDA zu bauen, der genau diese Sprache akzeptiert.

Beweisidee

Als Konzept wollen wir den Beweis folgend aufbauen: Wenn eine Sprache kontextfrei sit, dann gibt es einen PDA, der sie erkennt.

Sei dafür etwa $A$ eine kontextfreie Sprache. Nach Definition gibt es eine kontextfreie Grammatik $G$, welche sie erzeugen kann. Wir konstruieren dann einen PDA $P$ der ebene $G$ erzeugen kann, also alle Wörter $w\in G$ beschreiben / akzeptieren wird.

Für die Konstruktion: $P$ beginnt mit der Startvariable $S$ aus $G$ und pusht diese auf den Stack. Anschließend wird - nicht-deterministisch! - jede Regel von $G$ angewandt, um mögliche Satzstrukturen erzeugen zu können. Das passiert durch das Anwenden / Ausführen der Ersetzungsregel einzelner Variablen. Wir werden irgendwann einen String erhalten, der nur noch Terminale aufweist, wir haben also den String erfolgreich mit der Grammatik darstellen können !

[!Warning] Problem in dem Ansatz? Es stellt sich die Frage, wie intermediäre Strings gespeichert werden sollen. Auf dem Stack past nicht, weil hier die Eingabe durchlaufen und ersetzt werden muss.

Alternative: Man kann zusätzliche Übergänge einbauen, sodass nach einem einsetzen die Terminalvariablen vom Input weggestrichen werden (also schon als Erledigt markiert und terminiert werden). Dadurch folgt, dass auf dem Stack dann immer nur eine Variable steht!

Beweis | Sprache ist kontextfrei $⟹\exists$ PDA, der sie erkennt

Wir wollen jetzt also einen PDA bauen, der eine Sprache erkennt. Ferner soll diese dann kontextfrei sein!

Sei also $A$ eine kontextfreie Sprache mit zugehöriger kontextfreier Grammatik $G$. Wir konstruieren jetzt den PDA $P$ aus der Grammatik $G$, der $w$ akzeptiert, wenn es durch $G$ erzeugt werden kann.

1. Markiere das Ende des Stacks mit $\#$
2. Wir pushen die Startvariable $S$ von $G$ auf den Stack!
3. Jetzt wiederholen wir folgenden Ablauf:
   1. Wenn das oberste Symbol auf dem Stack eine Variable ist, dann ersetze sie nichtdeterministisch durch eine der rechten Seiten einer Regel aus $G$ und pushe die rechte Seite der Regel auf den Stack
   2. Wenn das oberste Symbol auf dem Stack ein Terminalsymbol ist, dann lese das Terminalsymbol von der Eingabe und POP es vom Stack, wenn es übereinstimmt (also erlaubt ist). Falls das nicht passt, beenden wir den Pfad ohne zu akzeptieren ->> die Ersetzung war scheinbar falsch und somit probieren wir es mit einer anderen Regel nochmal
   3. Wenn der Stack nun leer ist, also $\#$ auftritt, dann gehen wir in den akzeptierenden Zustand (wir konnten komplett verarbeiten). Das gilt nur, wenn wir die Eingabe komplett gelesen haben, sonst gilt es nicht.

[!Warning] Problem bezüglich der Übergangsfunktion Wir haben hier ein Problem, da wir bei den Grammatiken nur erlaubt haben, dass ein einzelnes Symbol $y$ erlaubt wird / auf den Stack gelegt werden darf.

Also $\delta (q,a,x)=\{(q^{\prime },y)\}$ ein neues Symbol kommt hinzu Wir wollen aber folgende Strukturen erlauben: $yAz$ soll auf den Stack gelegt werden. Wir können das umsetzen, denn CFGs haben die Struktur, dass Regeln nach rechts endliche Strings erzeugen (müssen). ->> Solche endlichen Ersetzungen können wir dann also durch zusätzliche Zustände $q_1^{\prime },q_2^{\prime },q_3^{\prime }\dots$ im PDA mit einem einfachen $\epsilon$-Übergang erlauben / erzeugen. also etwas wie $\delta (q,a,x)=\{(q_1^{\prime },y)\}$ und dann $\delta (q_1^{\prime },\epsilon ,\epsilon )=\{(q_2^{\prime },A)\},\delta (q_3^{\prime },\epsilon ,\epsilon )=\{(q^{\prime },z)\}$. Das kann man entsprechend verkürzen zu: $\delta (q,a,x)=\{(q^{\prime },yAz){\}}^{\prime }$

Wir wollen jetzt den Automaten entsprechend beschreiben:

–> Die Zustände von $P$ sind also ferner gegeben als: $\{q_{start},q_{loop},q_{end}\}\cup E$ wobei $E$ die Menge von zusätzlichen Hilfsvariablen ist, die wir brauchen, um die Ersetzungen aus $G$ dann in den Stack zu speichern. $q_{end}$ ist der einzige akzeptierende Zustande in dieser Betrachtung!

Wir möchten jetzt folgende Regeln beschreiben, die anschließend im Automaten genutzt werden können.

1. $\delta (q_{start},\epsilon ,\epsilon )=\{(q_{loop},S)\}$ –> Wir starten mit der Startvariable $S$ auf dem Stack (die wir anschließend nach und nach verarbeiten werden.)
2. aufgegliedert in zwei sich wiederholende Prozesse:
   1. $2.1$: $\delta (q_{loop},\epsilon ,A)=\{(q_{loop},w)\}\mid \forall A\to w\in G$ Ersetze eine vorhandene Variable $A$ gemäß aller Regeln der Grammatik
   2. $2.2:$ $\delta (q_{loop},a,a)=\{(q_{loop},\epsilon )\}$ Wir popen also das Terminalsymbol $a$
3. Wenn nun der Stack leer ist: $\delta (q_{loop},\epsilon ,\#)=\{(q_{end},e)\}$ springen wir über
4. alle anderen Übergänge führen nach undefined!

\usepackage{tikz}

\begin{document}

\begin{tikzpicture}[scale=0.2]
\tikzstyle{every node}+=[inner sep=0pt]
\draw [black] (25.7,-11.8) circle (3);
\draw (25.7,-11.8) node {$q1$};
\draw [black] (25.7,-26.1) circle (3);
\draw (25.7,-26.1) node {$q2$};
\draw [black] (25.7,-39.7) circle (3);
\draw (25.7,-39.7) node {$q3$};
\draw [black] (25.7,-39.7) circle (2.4);
\draw [black] (25.7,-14.8) -- (25.7,-23.1);
\fill [black] (25.7,-23.1) -- (26.2,-22.3) -- (25.2,-22.3);
\draw (25.2,-18.95) node [left] {$eps,esp\mbox{ }->S$};
\draw [black] (28.38,-24.777) arc (144:-144:2.25);
\draw (32.95,-26.1) node [right] {$2.1$};
\fill [black] (28.38,-27.42) -- (28.73,-28.3) -- (29.32,-27.49);
\draw [black] (23.02,-27.423) arc (-36:-324:2.25);
\draw (18.45,-26.1) node [left] {$2.2$};
\fill [black] (23.02,-24.78) -- (22.67,-23.9) -- (22.08,-24.71);
\draw [black] (14.4,-11.8) -- (22.7,-11.8);
\draw (13.9,-11.8) node [left] {$start$};
\fill [black] (22.7,-11.8) -- (21.9,-11.3) -- (21.9,-12.3);
\draw [black] (25.7,-29.1) -- (25.7,-36.7);
\fill [black] (25.7,-36.7) -- (26.2,-35.9) -- (25.2,-35.9);
\draw (25.2,-32.9) node [left] {$eps,\#->\mbox{ }eps$};
\end{tikzpicture}

\end{document}

Somit haben wir einen Automaten gebaut, welcher genau die Worte akzeptiert, die die Grammatik $G$ erlaubt.

Beweis | PDA erkennt Sprache $⟹$ Sie ist kontextfrei

Idee: Wir wollen analog zu Kleene’s Algorithmus für Finite State Automates eine kontextfreie Grammatik konstruieren, deren Produktion alle möglichen Übergänge des PDA zwischen div. beliebigen Zuständen mit unverändertem Stack beschreiben kann. Dann enthält diese insbesondere alle Worte die Übergänge vom Start mit leerem Stack zu Accept mit leerem Stack beschreiben.

Beweis:

Wir wollen hier ähnlich vorgehen

–> Wir betrachten diese Umstrukturierung jetzt quasi als ein flush.

Ferner konstruieren wir den Automaten so, dass er für jeden Übergang entweder etwas popt oder pushed.

• Immer dann, wenn er gleichzeitig was popt/pushed, dann werden wir diesen so aufteilen, dass es zwei Übergänge sind.

Wenn er weder was pushed/popt, dann legen wir ein random Sonderzustand / Zeichen auf den Stack und löschen es direkt danach wieder –> Es geht hier darum, dass wir somit einfach die Idee, dass jede Operation etwas entfernt / hinzufügt, erhalten bleibt und wir somit die Eigenschaft nicht verletzten.

Wenn wir den Zeitverlauf betrachten, sehen wir, dass der Automat bzw. dessen Stacks nie leer sein wird.

• Sei also $P$ ein PDA. Wir wollen jetzt eine kontextfreie Grammatik $G$ konstruieren, die alle Worte erzeugt, die von $P$ akzeptiert werden. Dabei ist ok wenn $G$ teils noch mehr kann, als unser PDA!
• $G$ wird folgend konstruiert: Für jedes paar $p,q$ von Zuständen $\delta$ geben wir in der Grammatik eine Variable $A_{pq}$ an, welche alle die Strings erzeugt, die $P$ von p mit einem leeren Stack zu $q$ mit einem leeren Stack bringt. Jeder dieser Übergänge kann dann auch $p$ mit beliebigem Stack zu $q$ bringen (solang sich der Stack nicht ändert)!
• Um das in der Konstruktion zeigen zu können, passen wir den Automaten so an, dass jetzt hier nur noch ein einziger akzeptierender Zustand vorhanden und genutzt werden kann.
  • Dass das gut funktioniert haben wir in 112.82_ueb02 gesehen. Also es zeigen einfach alle akzeptierenden Zustände mit einem $\epsilon$-Übergang auf den einzigen akzeptierenden Zustand.
• Ferner bauen wir den Automaten so um, dass er pro Schritt entweder pushed oder popt! Dafür ersetzen wir folgend
  • alle Regeln $\delta (q,a,A)=\{(q^{\prime },B)\}$(welcher pushed und popped), durch $\delta (q,a,A)=\{(q^{\prime \wedge },\$)\}$ und weiter $\delta (q^{\prime \wedge },\epsilon ,\$)=\{(q^{\prime },B)\}$ (also Aufteilung in entweder pop/push!)
  • Weiterhin ersetzen wir alle Regeln $\delta (q,a,\epsilon )=\{(q^{\prime },\epsilon )\}$ (es passier kein push oder pop) zu folgender Operation (wir wollen immer mind push/pop) = $\delta (q,a,\epsilon )=\{(q^{\prime \wedge },\$)\}$ und ferner, $\delta (q^{\prime \wedge },\epsilon ,\$)=\{(q^{\prime },\epsilon )\}$ -> wir pushen und poppen also redundant, damit wir die Grundregel einhalten, dass wir immer eins von beiden durchführen!
• Dadurch folgt: Variablen $A_{pq}$ folgen einer bestimmten Struktur, welche den rekursiven, kontextfreien Aufbau von $G$ erlaubt!

Mit dieser Definition von $A_{pq}$ resultieren wir jetzt, dass diese Variable alle STrings $x$ generieren soll, welche von $P$, von $p$ mit leerem Stack! zu $q$ mit leerem Stack führen.

• Dabei muss $x$ mit einem Push anfangen -> P wird ja in jedem Schritt nur pushen/poppen und der Keller ist anfangs leer!
• Ferner muss $x$ mit einem Pop aufhören -> In jedem Schritt push/pop passiert und der Stack am Ende leer sein muss

Daraus kommen zwei Möglichkeiten:

1. Das Symbol, was zu Beginn gepusht wurde, ist das gleiche, wie das, das zum Ende gepopt wird.
   1. Daraus folgt, dass der Stack O.B.d.A währen des Verlaufs hier nie leer ist ( sonst würde der Übergang der beiden gleichen Zustände woanders passieren)
   2. Dadurch können wir eine neue Regel einfügen: $A_{pq}\to a{A}_{rs}b$, wobei $a$ die gelesene Eingab nach $p$ ist und $b$ die letzte gelesen Eingabe ist. Ferner ist $r$ der Zustand nach $p$ und mit $s$ meinen wir die Eingabe, die anschließend zu q übergehen wird. Also folglich $p{\to }^{a}r\to \cdots \to s{\to }^{s}q(b)$
2. Die andere Möglichkeit: Das Symbol, dass zu Beginn gepushed wurde, ist ein anderes als das, was am Ende gepopt wird. Dann muss der Stack aber zwischenzeitlich leer gewesen sein!
   1. Dafür fügen wir auch eine neue Regel ein: $A_{pq}\to A_{pr}{A}_{rq}$ also wir haben zwei Regeln aufgesetzt, die die Ursprungs-Regel da aufteilen, wo der Stack leer sein wird/würde. Das passiert bei Zustand $r$!

Jetzt wurden alle Regeln erzeugt, die $P$ von beliebigem $p$ nach $q$ mit beliebigem aber gleichen Stack bringen. –> Sie sind kontextfrei!

Aus der obigen Definition und der Einsicht, dass wir also zwei Möglichkeiten bei Übergängen haben, folgt jetzt für die Konstruktion der Produktion einer Grammatik folgendes:

1. $\forall p,q,r,s\in Q,u\in \Gamma ,a,b\in {\Sigma }_{\epsilon }$ mit $(r,u)\in \delta (p,a,\epsilon )$ und $(q,\epsilon )\in \delta (s,b,u)$ fügen wir jetzt bei $G$ die Regel $A_{pq}\to a{A}_{rs}b$ hinzu, was wir ja zuvor bereits gezeigt/gebildet haben.
2. $\forall p,q,r\in Q$ fügen wir für $G$ die Regel $A_{pq}\to A_{pr}{A}_{rq}$ hinzu
3. $\forall p\in Q$ fügen wir für $G$ außerdem noch die Regel $A_{pp}\to \epsilon$ hinzu

Wir ziehen ein erstes Resultat aus der Konstruktion:

[!Satz] Folgerung Wenn $A_{pq}$ das Wort $x$ erzeugt, dann geht $P$ auf Eingabe $x$ von $p\to q$ mit leerem Stack

Beweis durch Induktion: IA: Wenn $x$ in einer einzigen Produktion entsteht, kann deren rechte Seite nur Terminal enthalten. Es gibt nur eine Regel in der Grammatik: $A_{pp}\to \epsilon$ und sie erzeugt ferner das leere Wort. Der PDA geht auf dem leeren Wort von $p\to p$ mit leerem Stack!

IS: Angenommen $A_{pq}$ erzeugt $x$ in $k+1$ Schritten und die vorherige Behauptung ist wahr für alle Übergänge der Länge $k$. Der erste Schritt der Erzeugung von $x$ ist dann entweder $A_{pq}\to a{A}_{rs}b$ oder eben $A_{pq}\to A_{pr}{A}_{rq}$. Im ersten Fall: ist dann $x=ayb$ und $A_{rs}$ erzeugt ferner $y$. Gemäß der Annahme IA geht dann $P$ auf $y$ von $r$ nach $s$ mit einem leeren Stack. Da dann $A_{pq}\to a{A}_{rs}b$ in $G$ist (wie gezeigt), gibt es dann gemäß der Konstruktion also ein $u\in \Gamma$, sodass dann jetzt $\delta (p,a,\epsilon )\ni (r,u)$ und ferner auch $\delta (s,b,u)\ni (q,\epsilon )$. Also geht dann $P$ auf $ayb$ von $p\to q$ mit einem leeren Stack! zweiter Falle: Hier ist dann $x=yz$ und $P$ geht unter $y$ und $z$von $p\to r$ und von $r\to q$ mit einem leeren Stack!

Ferner können wir noch eine zweite Erkenntnis erhalten: Wenn $P$ auf $x$ von $p\to q$ mit leerem Stack übergeht, dann erzegut $G$ auch $x$ aus $A_{pq}$!

Beweis (Via Induktion über die Länge der Berechnung von $P$ auf $x$)

• IA: Wenn $P$ in 0 Schritten übergeht, dann ist $x=\epsilon$ und somit $p=q$. Damit dann $A_{pp}\to \epsilon$ was passt.
• IS: Angenommen $P$ geht in $k+1$ Schritten von $p\to q$ mit leerem Stack über. Ender der Keller ist dazwischen durchweg nichtleer - weil Infos dazukommen etc - oder er ist zwischendurch mindestens einmal leer.
  • Im ersten Fall wird zu Beginn und Ende das gleiche Symbol $u$ gepushed/poptm, jeweils auf einem Übergang von $p$ auf (a,u) nach r, und von r dann auf (b,u) nach q, was genau der Umformung $A_{pq}\to a{A}_{rs}b$ entspricht! Es gibt dann also ein $y,x=ayb$ ist! Die Berechnung von $P$ auf $y$ ist dabei dann von Länge $k+1-2=k-1$ also geht nach IA $P$ unter $y$ von $r$ nach $s$ ohne das Symbol $u$ im Stack zu berühren!
  • Im zweiten Fall wird der Keller zwischendurch nach $<k$ Schritten einmal geleert (flushed) und somit gilt: $A_{pq}\to A_{pr}{A}_{rq}$ ist in $G$! Daher gent dann auch $p$ auf $r$ und $r$ auf q im Stack

Was wir aus dem Beweis ziehen können: Wir können in der Betrachtung des Kellerautomaten eine Grammatik beschreiben, die uns dabei hilft, solche Wörter kontextfrei bilden zu können.

Schlussfolgerung :

• manchmal hilft nicht-determinismus tatsächlich
• Wir brauchen dennoch ein Rechenmodell mit sinnvollem Speicher. Ein Stack ist nicht ausreichend, es gibt weiterhin Sprachen, die wir damit nicht beschreiben können.

Weiter gehts mit [[112.08_grammatiken]] und anschließend einem besseren Automaten: 112.12_turing_maschinen!