Update: Fehler im Automaten behoben.

Letzter Beitrag zum Thema... ich tippe besonders langsam, versprochen

Lernziel 5

Was sind determinierte Kellerautomaten?

Wir könnten zwar mit nichtdeterministischen Kellerautomaten leben und würden es sogar. Aber es gibt da ein Problem: wir können sie technisch nicht realisieren.

Den determinierten Kellerautomaten hatten wir im vorherigen Beitrag auch bereits definiert. Uns interessiert deshalb nicht was sie sind, sondern vielmehr wie sie sich von nichtdeterministischen Kellerautomaten unterscheiden und was das für Auswirkungen auf die erkannte Sprachklasse hat.

Eine echte Teilmenge der von nichtdeterminierten Kellerautomaten erkannten, kontextfreien Sprachen ist die deterministische kontextfreie Sprache:

Deterministisch kontextfrei

Eine Sprache ist deterministisch kontextfrei wenn es einen determinierten Kellerautomaten gibt, der sie erkennt.

Das Erkennen bedeutet folgendes:

Wenn $L\subseteq\Sigma^{*}$ eine deterministisch kontextfreie Sprache ist, dann gibt es einen Kellerautomaten $A=(\Sigma,\Gamma,\$,Q,q_0,\{q_{+}\},\delta)$ mit einem Zustand $q_{-}\in Q$, so dass für alle Worte $\omega\in\Sigma$ gilt:

$\omega\in L\Leftrightarrow (q_0,\omega\$,\$)\vdash^{*}(q_{+},\$,\epsilon)$

Das Wort $\omega$ ist Teil der deterministisch kontextfreien Sprache wenn es eine Überführungsfolge im Automaten $A$ gibt, die ausgehend vom Anfangszustand in einen akzeptierenden Endzustand mündet und die Eingabe zu Ende gelesen wurde, wobei der Keller leer ist.

$\omega\notin L\Leftrightarrow (q_0,\omega\$,\$)\vdash^{*}(q_{-},\$,\epsilon)$

Das Wort $\omega$ ist nicht Teil der deterministisch kontextfreien Sprache wenn es eine Überführungsfolge im Automaten $A$ gibt, die ausgehend vom Anfangszustand in einen nicht-akzeptierenden Endzustand mündet und die Eingabe zu Ende gelesen wurde, wobei der Keller leer ist.

Sie ist zudem auch noch eindeutig:

Jede deterministisch erkannte Sprache ist eindeutig*.

* erinnert Ihr euch noch an die Eindeutigkeit? Fall nicht: jedes abgeleitete Wort einer eindeutigen Sprache/Grammatik hat nur einen einzigen Ableitungsbaum.

Wir zeigen gleich, dass die deterministischen Automaten weniger leistungsfähig sind. Folgende Überlegungen sind notwendig:

1. ein deterministischer Kellerautomat akzeptiert nur Worte, die er zu Ende liest. Wir müssen daher unseren deterministischen Automaten entsprechen ummodellieren und die Szenarien vermeiden, wo der Automat nicht weiterlesen kann:

a) Keller leer bevor Eingabe zu Ende.

Lösung: neues Keller-Leerheits-Zeichen, dass nie gelöscht wird.

b) keine Folgekonfiguration für aktuelle Konfiguration vorhanden

Lösung: Vervollständigen von $\delta$, so dass wir zu jeder Möglichkeit einen Folgezustand haben

c) das Erreichen eines Zyklus, wo der Kopf nicht bewegt wird

Lösung: Erkennen und vermeiden des Zyklus.

2. Wir haben einen ausgezeichneten, positiven Endzustand: entweder er akzeptiert das Wort und wir landen in $q_{+}$ oder nicht und wir landen in $q_{-}\in Q$.

Mit der Vorarbeit aus dem letzten Beitrag, ist es nicht schwer diese weiteren Einschränkungen nachzuvollziehen.

Der Beweis für die Komplementbildung gelingt durch simples Vertauschen der Zustände $q_{+}$ und $q_{-}$, so dass wir diese Eigenschaft zusammenfasen können:

Sei $L\subseteq\Sigma^{*}$ deterministisch kontextfrei, so ist es auch $\Sigma^{*}\setminus L$.

Antwort zum Lernziel: Kellerautomaten (PDAs) sind endliche Automaten, die durch einen Kellerspeicher erweitert wurden. Bei einem Kellerautomaten wird ein Wort dann erkannt wenn der Keller leer ist oder der Automat in einem Endzustand landet (oder beides gleichzeitig).

Für einen determinierten Kellerautomaten gilt zudem, dass es für jedes Eingabezeichen und jedes oberste Kellerzeichen nur einen Zustandsübergang gibt, so dass der Kellerautomat den Berechnungsweg nicht zufällig wählen kann. Ist das nicht der Fall und gibt es zu einem Eingabezeichen und einem obersten Kellerzeichen mehrere mögliche Folgezustände, so ist der Kellerautomat nichtdeterministisch.

Für eine deterministisch kontextfreie Sprache $L$ bedeutet es, dass wir in jedem Fall für ein Wort $\omega\in L$ nach endlich vielen Schritten die Endkonfiguration $(q_{+},\$,\epsilon)$ (ausgewiesener Endzustand, Ende der Eingabe, leerer Keller) oder für ein Wort $\omega\notin L$ $(q_{-},\$,\epsilon)$ (beliebiger Zustand aus $Q$, Ende der Eingabe, leerer Keller) erreichen.

Lernziel 6

Ist jede kontextfreie Sprache deterministisch? Mit Begründung!

Ein (für mich) etwas verständlicheres Beispiel habe ich in den Folien der HU-Berlin gefunden und würde das hier gerne anbringen. Nehmen wir zwei deterministisch kontextfreie Sprachen (DCFL), die von einem determinierten Automaten erkannt wird, z.B.

$L_1=\{a^i b^j c^k\mid i\neq j\}\in DCFL$ sowie

$L_2=\{a^i b^j c^k\mid j\neq k\}\in DCFL$.

Beide Sprachen sind deterministisch kontextfrei. Wir können also einen deterministischen Kellerautomaten angeben, der sie erkennt.

Um $L_1$ zu entscheiden, können wir uns z.B. darauf beschränken die $a's$ einzulesen, $A's$ in den Keller zu schreiben und anschließend die $b's$ einzulesen und die $A's$ aus dem Keller zu entfernen. Es sind drei Fälle zu unterscheiden:

1. Gab es weniger $a's$ als $b's$, so haben wir noch $b's$ auf dem Eingabeband, während der Keller bereits leer ist und alles ist gut.

2. Gab es mehr $a's$ als $b's$, so haben wir keine $b's$ auf dem Eingabeband, während noch $A's$ im Keller sind und alles ist immernoch gut.

3. Gab es die gleiche Anzahl $a's$ und $b's$, so haben wir einen leeren Keller just in dem Moment, wo wir keine $b's$ auf dem Eingabeband haben und das Wort wird abgelehnt.

Das gleiche Verfahren klappt auch mit $L_2$ (nur mit $b's$ und $c's$ statt mit $a's$ und $b's$).

Schauen wir uns doch eine weitere Sprache an:

$L_1\cup L_2 = \{a^i b^j c^k\mid i\neq j$ oder $j\neq k\}\in CFL\setminus DCFL$.

Wie man sieht, ist das eine Vereinigung der beiden Sprachen $L_1$ und $L_2$. Um das etwas anschaulicher zu machen, schauen wir uns die Mengen doch einmal mit $1\leq i,j,k\leq 2$ an:

$L2_1=\{abbc,abbcc,aabc,aabcc\}$

$L2_2=\{abcc,abbc,aabcc,aabbc\}$

$L2_1\cup L2_2 = \{abbc,abbcc,aabc,aabcc,abcc,aabbc\}$

Während wir für für $L2_1, L2_2$ und die Vereinigung der beiden Sprachen $L2_1\cup L2_2$ sogar einen endlichen Automaten angeben können, der sie erkennt (wir erinnern uns: das ist genau der Grund warum alle endlichen Sprachen sogar regulär sind, ein akzeptierender Zustand pro Wort reicht im endlichen Automaten aus um die Sprachen zu erkennen), gelingt es uns bei $i,i,k\in\mathbb{N}$ nur für $L_1$ sowie $L_2$ einen Kellerautomaten anzugeben, der die Sprache erkennt (wir müssen die Anzahl der Buchstaben beobachen können und können das nur mindestens mit einem Kellerautomaten. Mindestens weil Turingmaschinen als stärkstes Berechnungsmodell selbstverständlich auch gehen, denn sie können ja selbst Typ-0-Sprachen erkennen).

Weit mehr Probleme macht uns die Vereinigung! Das Problem mit ihr ist: sie ist zwar kontextfrei, aber nicht deterministisch kontextfrei. Denn dafür können wir keine deterministische Kellermaschine angeben, sie sie erkennt.

Woran liegt das? Wie wir oben gesehen haben, beobachten wir mit dem Keller nur eine Variable (die Anzahl unserer ersten, eingelesenen Buchstaben) und können so eine andere abhängig von dieser entscheiden. Das ist bei den Sprachen $L_1$ und $L_2$ ja kein Problem. Bei $L_1\cup L_2$ haben wir jedoch drei Variablen, die von einander abhängig sind. Denn wir müssen $j$ in Abhängigkeit von $i$ und $k$ in Abhängigkeit von $j$ prüfen. Das war's also mit dem Determinismus, denn wir haben mehrere Wege, die wir beschreiten müssen um am Ende einen zu finden, der funktioniert.

Die kontextfreie Grammatik für $L_1\cup L_2$ ist:

$S\rightarrow{DC \mid AE \mid B}$
$D\rightarrow{F\mid G}$
$F\rightarrow{aF \mid aFb \mid a}$
$G\rightarrow{Gb \mid aGb\mid b}$
$C\rightarrow{cC\mid\epsilon}$

$A\rightarrow{aA\mid\epsilon}$
$E\rightarrow{H\mid I}$
$H\rightarrow{bH\mid bHc\mid b}$
$I\rightarrow{Ic \mid bIc \mid c}$

$B\rightarrow{J \mid K}$
$J\rightarrow{aJ\mid aJc\mid aL}$
$K\rightarrow{Kc\mid aKc\mid Lc}$
$L\rightarrow{bL\mid\epsilon}$

Und daraus können wir den zugehörigen Automaten nach dem Schema aus dem vorherigen Beitrag bauen:

Download: AiBjCk_NPDA_JFLAP-Datei

Damit haben wir auch eine wesentliche Aussage für das nächste Lernziel herausgearbeitet: dass wir keinen deterministischen Automaten für $L_1\cup L_2$ angeben können liegt daran, das die deterministisch kontextfreien Sprachen zwar abgeschlossen sind bzgl. Schnitt und Komplement, aber nicht gegen Vereinigung, Durchschnitt, Spiegelung und Konkatenation! Und das obere Beispiel war die Vereinigung. Beispiele für Durchschnitt, Spiegelung und Konkatenation überlasse ich erstmal euch

Zusammengefasst: Wir haben mit dem deterministischen Kellerautomaten, welche die Sprache erkennt, tatsächlich eine Beschneidung der Möglichkeiten, die uns ein nichtdeterministischer Kellerautomat bietet: wir können nicht mehr zwischen Berechnungspfaden wählen und sind an unsere Wahl "gebunden". War sie falsch, so landen wir in einer Sackgasse und damit war es das. Bei einem nichtdeterministischen Automaten haben wir währenddessen (durch mehrere Folgekonfigurationen für eine Konfiguration) bereits andere Wege parallel beschritten, wo uns einer (wenn wir einen korrekten Automaten angegeben haben) schon zur Lösung führen wird. War eine Berechnung falsch, so landen wir auf diesem einen Weg in einer Sackgasse und ... es ist uns egal. Wir haben ja noch genug andere Wege, die wir parallel beschreiten.

Hauptsache wir können beweisen, dass min. einer dieser Wege zu einem Ergebnis führt und entscheidet ob ein Wort sich in der Sprache befindet. Tut es das nicht, kann der nichtdeterministische Automat von uns aus solange weiterrechnen, bis er schwarz wird.

Ein Blick aus einer anderen Brille: Um bei der Sprache $L_1\cup L_2$ entscheiden zu können ob ein Wort tatsächlich zur Sprache gehört oder nicht, ist der Algorithmus wirklich einfach: Wir zählen die $a's$, $b's$ und $c's$, speichern die Anzahl auf dem Hilfsband und vergleichen die drei Variablen nachdem wir die Eingabe vollständig eingelesen haben miteinander. Ihr habt sicher schon eine TM im Kopf, die das macht. Während wir das also mit einer DTM problemlos machen können, schaffen wir das mit einem PDA durch die Einschränkungen leider nicht.

Antwort zum Lernziel: Nicht jede kontextfreie Sprache ist deterministisch. Es gibt kontextfreie Sprachen, die aufgrund ihrer Struktur nicht von einem PDA erkannt werden können weil ihr Aufbau von mehreren Variablen abhängt, diese jedoch nicht durch einen einzigen Kellerspeicher deterministisch abgebildet werden können. Erst durch das Beschreiten mehrerer Berechnungspfade ist es möglich auch mehrere Variablen in die Betrachtung einzubeziehen und aus der so generierten Vielzahl an Pfaden die Aussage zu treffen, dass einer in jedem Fall zum Ziel führt wenn das Wort sich in der Sprache befindet.

Eine solche kontextfreie, aber nicht deterministische Sprache lässt sich durch Vereinigung, Konkatenation, Durchschnitt oder Spiegelung einer oder mit mehreren deterministisch kontextfreien Sprachen erzeugen, da die Sprachklasse der deterministisch kontextfreien Sprachen nicht abgeschlossen gegen diese Operationen ist.

Lernziel 7

Sind die kontextfreien bzw. deterministisch kontextfreien Sprachen abgeschlossen unter Vereinigung, Durchschnitt, Komplement und Schnitt mit regulären Mengen?

Was soll ich hier schreiben? Reicht die Tabelle aus dem Skript? Ihr solltet euch noch einmal vor Augen führen, wie die Sprachklassen zusammenhängen und die Beziehungen zwischen Unter- und Oberklasse sind. Dann wird euch auch deutlich warum diese gegen gewisse Operationen nicht abgeschlossen sein können. Vielleicht schreibe ich später noch ein paar Sätze dazu, aber bis dahin:

Antwort zum Lernziel:

Lernziel 8

Welche der folgenden Probleme sind für kontextfreie Grammatiken entscheidbar/unentscheidbar? Wortproblem, Endlichkeitsproblem, Leerheitsproblem?

Hier sollten wir einige Probleme auf den Mengen entscheiden können, diese sind:

• Wortproblem: ob sich ein Wort $\omega$ in der Sprache $L$ befindet (oder nicht).
• Inklusion: ob die Worte einer Sprache $L_1$ in einer anderen Sprache$L_2$ enthalten sind
• Äquivalenz: ob die Sprache $L_1$ die gleiche Sprache wie $L_2$ ist.
• Leerheit: ob die Sprache leer ist, d.h. wir können mir der Grammatik, die die Sprache erzeugt keine Wörter erzeugen. Achtung: jede leere Sprache ist regulär.
• Endlichkeit: ob die Sprache endlich ist (endliche Sprache = reguläre Sprache = endlicher Automat)
• Universalität: ob die Sprache alle Kombinationen der Elemente aus dem Alphabet $\Sigma$ umfasst
• Eindeutigkeit: ob es für ein Wort nur einen Ableitungsbaum gibt.
• Determiniertheit: es gibt einen deterministischen Kellerautomaten, der entscheidet ob $\omega$ zur Sprache gehört oder nicht.

Antwort zum Lernziel:

Damit haben wir auch die letzte Kurseinheit durch. Hoffentlich konntet Ihr etwas mit den Zusammenfassungen anfangen und es haben sich keine Fehler eingeschlichen. Wenn doch: ab damit in die Kommentare!

Update 2: Einzel- und Mehrschrittrelationen, sowie Überführungsfunktion genauer erklärt.

Großes Update: Fehlerbeseitigung und langes Beispiel zum Beweisverfahren Sprache zu Automat(en) zu Grammatik zu Sprache (Lernziel 4).

Lernziel 3

Wie sind Kellerautomaten und die von ihnen akzeptierte Sprache definiert?

Noch einmal zur Auffrischung: alle Sprachen, die ein endlicher Automat akzeptiert sind regulär. Haben wir aber eine nicht reguläre Sprache, von was wird sie dann akzeptiert? Ein schönes Beispiel gab es (schon wieder) im Buch von Dirk W. Hoffmann mit der Sprache:

$LC_2=\{a^n b^n\mid n\in\mathbb{N}\}$

Wir brauchen also einen Automaten, der unsere Sprache akzeptiert. Mit dem Pumping Lemma für reguläre Sprachen sehen wir sofort, dass sie nicht regulär ist. Auch wenn wir es versuchen, so gelingt es uns nicht einen endlichen Automaten für diese Sprache zu bestimmen. Wir schaffen das immer nur für eine endliche Teilmenge der Sprache (durch akzeptierende Zustände für jedes Wort aus der Sprache) und wir wissen ja, dass jede endliche Sprache auch regulär ist weil wir im schlimmsten Fall einfach nur einen akzeptierenden Zustand für jedes Wort bauen müssen. Zwar ist das bei einer endlichen Teilmenge unserer Sprache $LC_2$ nicht notwendig; der endliche Automat kommt nur mit einem akzeptierenden Zustand aus, das Prinzip sollte aber klar geworden sein. Jeder akzeptierende Zustand fungiert also als eine Art "Speicher".

Was müssen wir also tun um einen Automaten zu bekommen, der diese Sprache akzeptiert? Wir müssen uns irgendwo die Anzahl der $a's$ merken und sie mit der Anzahl der $b's$ vergleichen können. Wir brauchen also irgendeinen "unendlichen" Speicher, da wir ja auch etvl. ein unendlich langes Wort haben. Hier helfen uns die Zustände unseres endlichen Automaten nicht weiter, denn er ist... nunja... endlich.

Wir erweitern unseren endlichen Automaten einfach, so dass wir noch genau die kontextfreien Sprachen mit ihm akzeptieren/semi-entscheiden können.

Während in der Literatur häufig mit einem $5$-Tupel gearbeitet wird, hat das Skript eigene Vorstellungen und verwendet ein $7$-Tupel zur Definition eines Kellerautomaten. Zusätzlich zu den üblichen Dingen werden auch noch das Kellerstartsymbol $\$$ und die Menge der Endzustände $Q_f$ definiert. Ist vielleicht auch gar nicht schlecht, denn die Wikipedia sieht das ähnlich. Ich echauffiere mich also in den letzten Zügen des Skripts nicht über dasselbe. Wollen wir also formal definieren:

Kellerautomat

$A=(\Sigma,\Gamma,\S,Q,q_0,Q_f,\delta)$ mit

$\Sigma$ endliches Eingabealphabet

$\Gamma$ endliches Kelleralphabet

$\$\in\Gamma\setminus\Sigma$ Kellerstartsymbol und Markierung für Eingabeende

$q_0\in Q$ als Anfangszustand

$O_f\subseteq Q\Sigma$ Endzustände

$\delta$ Zustandsübergangsfunktion

Kommen wir nun zur Zustandsübergangsfunktion $\delta$. Ich würde sagen, dass ich ein paar Beispiele gebe anstatt vollständig formal zu bleiben:

$\delta(s_0,a,A):=\{(s_1,B)\}$

Im Zustands $s_0$, lese $a$ aus der Eingabe, nimm $A$ vom Kellerstapel, wechsle in den Zustand $s_1$ und schiebe $B$ auf den Kellerstapel.

$\delta(s_0,b,A):=\{(s_1,\epsilon)\}$

Im Zustands $s_0$, lese $b$ aus der Eingabe, nimm $A$ vom Kellerstapel, wechsle in den Zustand $s_1$ und lege nichts in den Kellerstapel. Damit wurde das Zeichen $A$ aus dem Keller gelöscht. Lag $A$ zu diesem Zeitpunkt nicht auf dem Stapel, kann die Übergangsfunktion nicht angewandt werden.

$\delta(s_0,\epsilon,\epsilon):=\{(s_0,\epsilon)\}$

Im Zustands $s_0$, lese nichts von der Eingabe, nimm nichts vom Kellerstapel, bleibe im Zustand $s_0$ und lege nichts in den Kellerstapel. 

Mittels $\vdash$ und $\vdash^n$ sowie $\vdash^{*}$ werden die Einzel- und Mehrschrittrelationen bezeichnet.

$(s_0,aaaa,AAA)\vdash(s_1,aaa,AA)$

Vom Zustands $s_0$ mit dem Wort $aaaa$ auf dem Eingabeband und $AAA$ im Keller, kann man in einem Schritt den Zustand $s_1$ erreichen, wobei dann nur noch $aaa$ auf dem Eingabeband und $AA$ im Keller steht.

$(s_0,ababa,AAA)\vdash^5(s_1,aaaa,AAAA)$

Vom Zustands $s_0$ mit dem Wort $ababa$ auf dem Eingabeband und $AAA$ im Keller, kann man in $5$ Schritten den Zustand $s_1$ erreichen, wobei dann $aaaa$ auf dem Eingabeband und $AAAA$ im Keller steht.

$(s_0,bb,AB)\vdash^{*}(s_1,\$,\$)$

Vom Zustands $s_0$ mit dem Wort $bb$ auf dem Eingabeband und $AB$ im Keller, hat man nach dem letzten, möglichen Berechnungsschritt den Zustand $s_1$ erreicht, wobei dann nichts auf dem Eingabeband und nichts im Keller steht.

Damit sind wir auch schon fast durch. Es gibt jedoch drei Dinge, die noch wichtig sind: der Automat hat zwei Wege eine Sprache zu erkennen

1. mittels Endzustand (wir landen in einem Endzustand)

Formal: $L(A) =\{\omega\in\Sigma^{*}\mid\exists q\in Q_f \exists X\in\Gamma^{*} (q_0,\omega\$,\$)\vdash^{*}(q,\$,X)\}$

"Für ein Wort über dem Alphabet $\Sigma$", ausgehend vom Startzustand $q_0$, während wir das Eingabewort und die Markierung für das Eingabeende auf dem Band haben ($\omega\$$) kommen wir nach endlich vielen Schritten zum Endzustand $q$, während auf dem Eingabeband der Kopf über dem Eingabeende $\$$ ist und irgendwas ($X$) im Keller steht"

2. mittels leerem Keller (wir landen zwar nicht einem Endzustand, aber der Keller ist leer)

Formal: $L(A) =\{\omega\in\Sigma^{*}\mid\exists q\in Q (q_0,\omega\$,\$)\vdash^{*}(q,\$,\epsilon)\}$

"Für ein Wort über dem Alphabet $\Sigma$", ausgehend vom Startzustand $q_0$, während wir das Eingabewort und die Markierung für das Eingabeende auf dem Band haben ($\omega\$$) kommen wir nach endlich vielen Schritten zum beliebigen Zustand $q$, während auf dem Eingabeband der Kopf über dem Eingabeende $\$$ ist und der Keller leer ist ($\epsilon$)"

Und die Definition des Determinismus einer Kellermaschine:

Ein Kellerautomat ist determiniert, wenn:

es zu jedem Eingabezeichen und jedem obersten Kellerzeichen maximal ein Zustandsübergang gibt.

Antwort zum Lernziel: die Kellerautomaten bestehen aus einem Eingabe- und einem Kelleralphabet, einem Kellersymbol und der Markierung für das Eingabeende sowie Anfangs- und Endzuständen und der Zustandsübergangsfunktion. Die von ihnen akzeptierte Sprache wird definiert als die Worte, die a) den Automaten entweder in einen Endzustand bringen wenn das Ende des Eingabewortes erreicht ist, wobei egal ist, was im Keller steht oder b) der Keller leer ist wenn das Ende des Eingabewortes erreicht ist, wobei es egal ist, in welchem Zustand sich der Automat zu diesem Zeitpunkt befindet.

Und das sind genau die kontextfreien Sprachen, die die Typ-2-Grammatiken erstellen können. Wie wir zu einer kontextfreien Grammatik einen Kellerautomaten basteln, zeigen wir im nächsten Abschnitt, indem wir die Produktionsregeln der Grammatik in die Übergänge unseres Kellerautomaten codieren.

Lernziel 4

Wie zeigt man, dass Kellerautomaten genau die kontextfreien Sprachen erkennen?

Ich würde hier noch ein paar Kleinigkeiten in eure Erinnerung rufen bevor wir mit den Kellerautomaten richtig loslegen. Das liegt u.a. daran, dass wir bei den vorher betrachteten Sprachen eine Äquivalenz zwischen TM und NTM hatten (wir können eine NTM durch eine TM simulieren indem wir einfach alle möglichen Berechnungspfade der NTM durchlaufen), bei den Kellerautomaten hier aber strikt trennen müssen. Nichtdeterministische Kellerautomaten sind eben nicht äquivalent zu deterministischen. Letztere spielen aber eine große Rolle, so dass wir noch später auf sie zurück kommen werden.

Um also zu zeigen, dass ein Kellerautomat genau die kontextfreien Sprachen erkennt, müssen wir zu einer kontextfreien Grammatik $G$ einen Kellerautomaten  $A$ angeben, der mit seinen zwei Akzeptanzmethoden (leerer Keller und Endzustand) ein Wort $\omega$ genau dann akzeptiert wenn das Wort mittels der kontextfreien Grammatik $G$ abgeleitet werden kann. Es muss also gelten:

$L(G) = L(A)$

Um zu zeigen, dass wir alle kontextfreien Sprachen durch Kellerautomaten erkennen lassen können, müssen wir das Regelschema der kontextfreien Grammatiken in ein Zustandsübergangsschema für Kellerautomaten umwandeln. Nur ein Problem haben wir: Die Frage welche Ersetzung (d.h. die Rückumwandlung der Ableitung) zu machen ist, müssen wir beantworten und tun das mit unserem Nichtdeterminismus, indem wir aus mehreren in Frage kommenden Ersetzungen einfach eine raten!

Ich würde sagen, dass wir auch hier direkt mit einem Beispiel starten und eine kontextfreie Grammatik in einen Kellerautomaten überführen.

Grammatik zum Automat mit einem Zustand: kontextfreie Grammatik $G_D=\{\Sigma,\Pi,R,S\}$ mit den Regeln $R$

$S\rightarrow\epsilon\mid SS\mid [S]\mid(S)$

soll überführt werden in einen Kellerautomaten $K_{G_D}=(\Sigma,\Gamma,S,Q,q_0,Q_f,\delta)$, der die gleiche Sprache $L(G_D)$ akzeptiert.

Ja, das ist die Dyck-Sprache. Geklaut aus dem Buch von Dirk W. Hoffmann. Sehr einfaches und leicht verständliches Beispiel. Wie kommen hier mit  nur einem Zustand aus und können den Kellerspeicher so effizient nutzen. Nun müssen wir erstmal $\Sigma,\Gamma,S,Q,q_0,Q_f,\delta$ des Automaten festlegen.

Kelleralphabet

$\Gamma=\Sigma\cup\Pi$ (unser Kelleralphabet besteht also aus Elementen des Terminal- und des Nonterminalalphabets.

Zustände

Die Regel $A\rightarrow\omega_1,...,\omega_n$ wird zu $\delta(s_0,\epsilon,A):=\{(s_0,\epsilon)\}$. In unserem Fall sind das:

$\delta(s_0,\epsilon,S):=\{(s_0,\epsilon)\}$

$\delta(s_0,\epsilon,S):=\{(s_0,SS)\}$

$\delta(s_0,\epsilon,S):=\{(s_0,[S])\}$

$\delta(s_0,\epsilon,S):=\{(s_0,(S))\}$

Dazu brauchen wir auch noch Regeln für die Terminalzeichen ($\delta(s_0,a,a):=\{(s_0,\epsilon)\}$), so dass nur mit der Verarbeitung weitergemacht werden soll wenn das oberste Zeichen im Keller mit dem eingelesenen Zeichen übereinstimmt:

$\delta(s_0,(,():=\{(s_0,\epsilon)\}$

$\delta(s_0,),)):=\{(s_0,\epsilon)\}$

$\delta(s_0,[,[):=\{(s_0,\epsilon)\}$

$\delta(s_0,],]):=\{(s_0,\epsilon)\}$

Zusätzlich müssen wir das Kellerstartsymbol durch $S$ ersetzen um loszulegen:

$\delta(s_0,\epsilon,\$):=\{(s_0,S)\}$

Achtung: wir haben hier ein Beispiel gezeigt, dass die Sprache mittels leerem Keller akzeptiert und nicht mittels Endzuständen! Das ist der Automat, der raus kommt ($Z$ ist das Kellerendzeichen und $\lambda$ ist unser leeres Wort $\epsilon$, bzw. beliebiges Zeichen):

Download: Dyck-Sprache JFLAP Datei

Der Automat ist nichtdeterministisch angelegt, d.h. es existieren mehrere Berechnungspfade für eine Eingabe. Das werdet Ihr sehen wenn Ihr den Automaten laufen lasst. Es geht uns beim Nichtdeterminismus ja nur darum mindestens einen Berechnungspfad zu haben, der durchläuft. Dass andere evtl. scheitern ist uns in diesem Sinne egal. Die Regeln beim Automaten bedeuten folgendes:

(1) $\lambda,Z,S\Rightarrow$Wenn auf dem Eingabeband ein Zeichen $\lambda$ (ein Zeichen nicht aus dem Alphabet) steht und das oberste Zeichen im Keller das Kelleranfangszeichen $Z$ ist, ersetze es im Keller mit $S$.

(2) $\lambda,S,\lambda\Rightarrow$Wenn auf dem Eingabeband ein Zeichen $\lambda$ und im Keller ein $S$ steht, so ersetze $S$ im Keller mit $\lambda$. Damit ist der Keller leer, es ist unsere "Endbedingung". Nicht vergessen: der Keller wird erst dann geleert (auf $\lambda$ gesetzt) wenn wir fertig mit dem Einlesen (es steht $\lambda$ auf dem Eingabeband) und am Ende im Keller nur ein $S$ stand, d.h. dass wir einen korrekten Berechnungspfad hatten und damit das Wort richtig abgeleitet wurde.

(3) $\lambda,Z,S\Rightarrow$Wenn auf dem Eingabeband ein Zeichen $\lambda$ steht und das oberste Zeichen im Keller das Zeichen $S$ ist, ersetze es im Keller mit $(S)$.

(4) $\lambda,Z,S\Rightarrow$Wenn auf dem Eingabeband ein Zeichen $\lambda$ steht und das oberste Zeichen im Keller das Zeichen $S$ ist, ersetze es im Keller mit $[S]$.

(5) $\lambda,Z,S\Rightarrow$Wenn auf dem Eingabeband ein Zeichen $\lambda$ steht und das oberste Zeichen im Keller das Zeichen $S$ ist, ersetze es im Keller mit $SS$.

Spätestens jetzt habt Ihr ein Fragezeichen über dem Kopf. Oder Ihr nickt. Oder ihr fragt euch, warum ich um den heißen Brei herumrede. Habt Ihr gemerkt? Welche Regel von den letzten drei wird nun angewendet wenn auf dem Eingabeband das Zeichen eines leeren Wortes $\lambda$ steht und das oberste Zeichen im Keller das Zeichen $S$ ist? Wird da nun ein $(S), [S]$ oder $SS$ draus? Tja, das genau ist der Nichtdeterminismus. Es kann alles sein. Und wenn wir den falschen Pfad wählen, können wir evtl. nie aus der Berechnung raus. Und wisst Ihr was? Es ist uns egal! Hauptsache es existiert ein Pfad, das reicht uns.

Nun kommen die wichtigsten Regeln:

(6) $],],\lambda\Rightarrow$Wenn auf dem Eingabeband das Zeichen $]$ steht und das oberste Zeichen im Keller ebenfalls $]$ ist, ersetze es im Keller mit $\lambda$.

(7) $[,[,\lambda\Rightarrow$Wenn auf dem Eingabeband das Zeichen $[$ steht und das oberste Zeichen im Keller ebenfalls $[$ ist, ersetze es im Keller mit $\lambda$.

(8) $(,(,\lambda\Rightarrow$Wenn auf dem Eingabeband das Zeichen $($ steht und das oberste Zeichen im Keller ebenfalls $($ ist, ersetze es im Keller mit $\lambda$.

(9) $),),\lambda\Rightarrow$Wenn auf dem Eingabeband das Zeichen $)$ steht und das oberste Zeichen im Keller ebenfalls $)$ ist, ersetze es im Keller mit $\lambda$.

Wir leeren mit diesen Regeln also unseren Keller. Es fällt euch wahrscheinlich schwer, zu verstehen was der Automat tut. Ich würde sagen, wir probieren ihn an einem kleinen Beispiel aus.

Funktionsweise: Wenn wir z.B. den Automaten mit der Eingabe $"()"$ laufen lassen, so passiert folgendes:

Ich habe nicht alle Pfade aufgemalt, sondern nur einen korrekten Pfad bis zum Ende durchgezeichnet. Die mit $...$ beschrifteten Pfade führen zu einer weiteren Berechnung (die evtl. auch in einem Ergebnis münden kann). Nach Anwendung der Regel $4$ und $2$ in der zweiten Ableitung gibt es für die Symbolkombination $\lambda,($ oder $\lambda,\lambda$ keinen weiteren Übergang und wir haben einen undefinierten Automatenzustand.

Bei den zwei weiteren Pfaden geht es jedoch weiter. Um den Keller zu leeren müssen wir als erstes Kellerzeichen und erstes Bandzeichen eines der vier Klammern haben. Da wir immernoch bei $($ als Eingabe sind, müssen wir es schaffen auf das Hilfsband eine öffnende Klammer $($ zu bekommen, was durch Anwendung der Regel 3 gut funktioniert. Bei den anderen drei Pfaden führt einer wieder in die Sackgasse, da wir keinen Folgezustand für die Symbolkombination $\lambda,[$ oder $(,[$ haben und die beiden anderen zu weiteren Berechnungspfaden.

Der für uns spannende Pfad wird durch Regel 3 verfolgt: es wird mit Regel 8 anschließend ein Zeichen auf dem Hilfsband gelöscht und wir lesen das nächste Zeichen, unsere schließende Klammer $)$ oder $\lambda$ ein und suchen für die Symbolkombination $\lambda,S$ oder $), S$ die nächsten, passenden Regeln. Es kommen wieder vier Berechnungspfade in Frage, die wir nun nicht weiter verfolgen. Sonst wäre die Grafik riesig geworden.

Mit Anwendung der Regel 2 ersetzen wir das $S$ im Keller durch $\lambda$ und können nun die einzig passende Regel $9$ für die Symbolkombination $),)$ anwenden um das nächste Zeichen (wir haben keins mehr) auf dem Eingabeband einzulesen und $)$ im Keller zu löschen.

Für Die Symbolkombination $\lambda,S$ haben wir wieder vier mögliche Regeln, die passen könnten. Aber nur Regel 2 führt uns zu einem leeren Keller beim erreichen des Eingabeendes. Und damit haben wir einen Pfad erfolgreich gefunden.

Wir haben hier zeigen können, dass wir mit nur einem Zustand auskommen. Daher sollte der wichtige Satz

Für jeden Automaten, der eine Sprache $L$ mittels Endzustand akzeptiert, existiert ein Automat, der die $L$ mittels leerem Keller akzeptiert und umgekehrt (Vorsicht: das gilt nicht für deterministische Kellerautomaten!).

nicht vergessen werden!

Wie konstruieren wir denn aus einem Automaten mit mehreren Zuständen einen mit nur einem Zustand? Ganz einfach:

1. Aus dem Automaten mit mehreren Zuständen wird eine kontextfreie Grammatik erzeugt (nach Rechenberg ist das immer möglich, hat aber keine praktische Bedeutung und wird deshalb in der Literatur ausgelassen. Tatsächlich habe ich in vier Büchern, die ich zur Hand habe den Weg anhand eines konkreten Beispiels nicht gefunden. Wer etwas findet, bitte Info an mich. Mit dem JFLOP könnt Ihr einen Automaten in eine Grammatik wandeln, evtl. schreibe ich das Verfahren einfach nochmal hierhin)

2. Aus der kontextfreien Grammatik wird mit dem oben angegebenen Verfahren ein Automat mit nur einem Zustand erstellt

That's it.

Zusammengefasst: Wir können also zu einer kontextfreien Sprache eine kontextfreie Grammatik $G$ angeben. Diese Sprache erkennt auch ein Kellerautomat mittels leerem Keller. Auch ein Automat mit Endzustand tut dies. Wir können sogar einen Automaten angeben, der nur mit einem Zustand auskommt, da die Mächtigkeit des Automaten nur von seinem Keller kommt.

Noch eine Kleinigkeit, die hier von Bedeutung ist: was ist unter einem normalisierten Automaten zu verstehen ist? Dieser spielt bei bei der Konvertierung von Automat zu Grammatik eine große Rolle (hier ist ein gutes Dokument der Fakultät für Informatik der Uni Illionois, die etwas mehr Details dazu hat, als ich hier wiedergebe):

1. Es gibt nur einen akzeptierenden Endzustand

Das tun wir, indem wir einen neuen Endzustand einführen und einen $\epsilon$-Übergang von den anderen Zuständen dorthin zeichnen

2. Vor der Akzeptanz wird der Keller geleert

Das kann man tun, indem man vor dem Endzustand in einen Zustand geht und alles bis zum Kellerendzeichen ($\$$) aus dem Keller schmeißt.

3. Beim Übergang wird entweder ein Zeichen aus dem Keller entnommen oder eines hineingelegt, aber nicht beides

Hier gibt es zwei Fälle: a) Übergänge, die ein Element aus dem Keller nehmen und ein neues hinein legen und b) Übergänge, die nichts tun. Beide können wir mit neuen Zuständen und Übergängen simulieren. Fall a) handeln wir ab, indem wir zwei neue Zustände einführen: einer entnimmt das Zeichen, geht in einen temporären (neuen) Folgezustand über, dann wird ein Zeichen hineingelegt und der eig. Folgezustand eingenommen. Fall b) behandelt wir noch einfacher: wir basteln uns zwei neue Übergänge. Einer nimmt das Zeichen, geht in den temporären (neuen) Folgezustand und der nächste legt es wieder zurück. Fertig.

Das war jetzt alles wahrscheinlich bisschen viel und verwirrend. Vielleicht hilft eine kurze Übersicht des Beweisverfahrens?

Beweisverfahren

Sprache $L\Rightarrow$

Kellerautomat $A\Rightarrow$

normalisierter Kellerautomat $\overline{A}\Rightarrow$

Grammatik $G\Rightarrow$

Sprache $L$ und Kellerautomat mit nur einem Zustand $A^{'}\Rightarrow$.

Damit schließt sich der Kreis. Wir zeigen der Vollständigkeit halber im letzten Schritt auch noch, dass wir mit dem oben genannten Verfahren aus der erzeugten Grammatik einen Automaten (nach dem oben gezeigten Verfahren) ableiten können, der nur einen einzigen Zustand hat und das Wort mittels leerem Keller akzeptiert.

Wollen wir den ganzen Spaß noch einmal an der Sprache vom Anfang des Beitrags durchspielen:

Beispiel: $LC_2=\{a^n b^n\mid n\in\mathbb{N}\}$

Sprache zu Kellerautomat

Dieser Automat erkennt die Sprache mit einem leeren Keller.

Kellerautomat zu normalisiertem Kellerautomat

Dieser Automat erkennt die Sprache mittels Endzustand. So sieht er aus:

Wie wir sehen, haben wir einfach nur einen neuen Endzustand eingeführt. Der folgende Automat erkennt also das Wort in einem Endzustand und hat auch noch einen leeren Keller. Also optimale Bedingungen. Damit ist er soweit normalisiert (bis auf den Punkt mit den Überführungsbedingungen: die tun immer noch zwei Schritte gleichzeitig (Push und Pop). Da sie uns aber bei der Grammatik nicht stören, war hier etwas faul, sorry!).

Normalisierter Kellerautomat mit Endzustand zu Grammatik

Nun wandeln wir die Zustandsübergänge des Automaten in die Regeln für die Grammatik um. Wir kümmern uns zunächst um alle Regeln, die etwas aus dem Keller entnehmen (nicht vergessen, im Bild ist $\lambda$ unser $\epsilon$)

1. $\delta(s_i,a,A)=\{(s_j,\epsilon)\}\Rightarrow s_{i}As_{j}\rightarrow a$

$\delta(s_0,b,A)=\{(s_1,\epsilon)\}\Rightarrow s_{0}As_{1}\rightarrow b$

$\delta(s_1,b,A)=\{(s_1,\epsilon)\}\Rightarrow s_{1}As_{1}\rightarrow b$

$\delta(s_1,\epsilon,Z)=\{(q_2,\epsilon)\}\Rightarrow s_{1}Zq_{2}\rightarrow\epsilon$

Jetzt wird es haariger. Was machen wir mit den verbliebenen Regeln? Problem hierbei: wir nehmen was aus dem Keller und legen gleichzeitig was drauf. Erinnert Ihr euch an die Kriterien für die Normalisierung? Nunja, eine haben wir hier nicht erfüllt: Nr. 3. Aber das macht erstmal nichts, wir generieren einfach ein paar Regeln mehr nach folgendem Muster:

2. $\delta(s_i,a,A)=\{(s_j,BC)\}\Rightarrow s_{j}As_{x}\rightarrow a(s_{j}Bs_{y})(s_{y}Cs_{x})$, wobei $s_x$ und $s_y$ alle Zustände im Automaten sind. Wir müssen also alle Zustandskombinationen abgrasen, was uns zur folgenden, langen Liste an Regeln führt:

Regel $a,A;AA$

$\delta(s_0,A,s_0)=\{(s_0,AA)\}\Rightarrow s_{0}As_{0}\rightarrow{a(s_{0}As_{0})(s_{0}As_{0})}$

$\delta(s_0,A,s_0)=\{(s_0,AA)\}\Rightarrow s_{0}As_{1}\rightarrow{a(s_{0}As_{0})(s_{0}As_{1})}$

$\delta(s_0,A,s_0)=\{(s_0,AA)\}\Rightarrow s_{0}Aq_{2}\rightarrow{a(s_{0}As_{0})(s_{0}Aq_{2})}$

$\delta(s_0,A,s_0)=\{(s_0,AA)\}\Rightarrow s_{0}As_{0}\rightarrow{a(s_{0}As_{1})(s_{1}As_{0})}$

$\delta(s_0,A,s_0)=\{(s_0,AA)\}\Rightarrow s_{0}As_{1}\rightarrow{a(s_{0}As_{1})(s_{1}As_{1})}$

$\delta(s_0,A,s_0)=\{(s_0,AA)\}\Rightarrow s_{0}Aq_{2}\rightarrow{a(s_{0}As_{1})(s_{1}Aq_{2})}$

$\delta(s_0,A,s_0)=\{(s_0,AA)\}\Rightarrow s_{0}As_{0}\rightarrow{a(s_{0}Aq_{2})(q_{2}As_{0})}$

$\delta(s_0,A,s_0)=\{(s_0,AA)\}\Rightarrow s_{0}As_{1}\rightarrow{a(s_{0}Aq_{2})(q_{2}As_{1})}$

$\delta(s_0,A,s_0)=\{(s_0,AA)\}\Rightarrow s_{0}Aq_{2}\rightarrow{a(s_{0}Aq_{2})(q_{2}Aq_{2})}$

Regel $a,Z;AZ$

$\delta(s_0,Z,s_0)=\{(s_0,AZ)\}\Rightarrow s_{0}Zs_{0}\rightarrow{a(s_{0}As_{0})(s_{0}Zs_{0})}$

$\delta(s_0,Z,s_0)=\{(s_0,AZ)\}\Rightarrow s_{0}Zs_{1}\rightarrow{a(s_{0}As_{0})(s_{0}Zs_{1})}$

$\delta(s_0,Z,s_0)=\{(s_0,AZ)\}\Rightarrow s_{0}Zq_{2}\rightarrow{a(s_{0}As_{0})(s_{0}Zq_{2})}$

$\delta(s_0,Z,s_0)=\{(s_0,AZ)\}\Rightarrow s_{0}Zs_{0}\rightarrow{a(s_{0}As_{1})(s_{1}Zs_{0})}$

$\delta(s_0,Z,s_0)=\{(s_0,AZ)\}\Rightarrow s_{0}Zs_{1}\rightarrow{a(s_{0}As_{1})(s_{1}Zs_{1})}$

$\delta(s_0,Z,s_0)=\{(s_0,AZ)\}\Rightarrow s_{0}Zq_{2}\rightarrow{a(s_{0}As_{1})(s_{1}Zq_{2})}$

$\delta(s_0,Z,s_0)=\{(s_0,AZ)\}\Rightarrow s_{0}Zs_{0}\rightarrow{a(s_{0}Aq_{2})(q_{2}Zs_{0})}$

$\delta(s_0,Z,s_0)=\{(s_0,AZ)\}\Rightarrow s_{0}Zs_{1}\rightarrow{a(s_{0}Aq_{2})(q_{2}Zs_{1})}$

$\delta(s_0,Z,s_0)=\{(s_0,AZ)\}\Rightarrow s_{0}Zq_{2}\rightarrow{a(s_{0}Aq_{2})(q_{2}Zq_{2})}$

3. Nun werden die Zustandskombinationen noch umbenannt in $A,B,C, ...$, unnötiges gestrichen (man kann sich einen Abhängigkeitsgraphen malen um unnötige Zustände besser zu identifizieren, wie z.B. in diesem Beitrag gezeigt) und der Startzustand $S\rightarrow s_0Zq2$ hinzugefügt. Am Ende haben wir dann die folgenden Regeln für unsere Grammatik:

$S\rightarrow aCA$

$C\rightarrow b\mid aCG$

$G\rightarrow b$

$A\rightarrow\epsilon$

 Wir könnten hier sogar noch $G$ oder $C$ streichen und kommen auf

$S\rightarrow aCA$

$C\rightarrow b\mid aCC$

$A\rightarrow\epsilon$

Grammatik zu Kellerautomat mit nur einem Zustand

Da wir nun unsere Grammatik haben, können wir nach dem Verfahren von oben (erstes Beispiel bei Lernziel 4) uns einen schönen Automaten mit nur einem Zustand basteln, der die Worte unserer Sprache mit leerem Keller akzeptiert. Das sind die Zustandsübergänge, die wir aus der Grammatik ableiten können:

$S\rightarrow aCA$

$\delta(s_0,\epsilon,A)=\{(s_0,aCA)\}$

$C\rightarrow b\mid aCC$

$\delta(s_0,\epsilon,C)=\{(s_0,b)\}$

$\delta(s_0,\epsilon,C)=\{(s_0,aCC)\}$

$A\rightarrow\epsilon$

$\delta(s_0,\epsilon,A)=\{(s_0,\epsilon)\}$

Fehlen uns noch die Regeln für die Terminale und die Ersetzung des Kellerzeichens durch erste Ableitung $S$ wenn wir fertig sind:

$\delta(s_0,a,a)=\{(s_0,\epsilon)\}$

$\delta(s_0,b,b)=\{(s_0,\epsilon)\}$

$\delta(s_0,\epsilon,Z)=\{(s_0,S)\}$

Nachdem wir alles zusammengefügt haben, kommt der folgende Automat heraus:

Grammatik zu Sprache

Letzter Schritt nochmal aus der Grammatik die ableitbare Sprache zu basteln:

$LC_2=\{a^n b^n\mid n\in\mathbb{N}\}$

Damit ist der Kreis geschlossen und wir sind da, wo wir angefangen haben. Und ich hoffe, dass ich mich nirgendwo vertippt habe...

Antwort zum Lernziel: zu jedem nichtdeterministischen Kellerautomat, der eine Sprache mittels Endzustand erkennt kann man einen nichtdeterministischen Kellerautomaten angeben, der dieselbe Sprache mittels leerem Keller (ohne Endzustand) erkennen kann. Und das sogar mit nur einem einzigen Zustand. Das liegt daran, dass die Ausdrucksstärke nur vom Keller und nicht von den Zuständen des Automaten kommt.

Dieser Automat kann weiter normiert werden, so dass man beim Erreichen des Endzustands einen leeren Keller hat und die Überführungsfunktionen entweder etwas auf den Stack legen oder nur etwas wegnehmen. Dazu werden die Überführungsfunktionen, die diese Kriterien nicht erfüllen durch neue, temporäre Zustände und neue Regeln ersetzt.

Der normierte Automat lässt sich dann einfacher in eine kontextfreie Grammatik umwandeln, das die gleiche Sprache erzeugt wie der normierte Automat. Dazu werden die Überführungsrelationen des Automaten in Ableitungsregeln für die Grammatik umgewandelt, ein Abhängigkeitsgraph gezeichnet und unnötige Zustände und Relationen mit seiner Hilfe gestrichen, so dass sich die Menge der Ableitungen auf ein Minimum verkürzt.

Am Ende hat man eine minimale Grammatik, aus der man zum einen die Sprache ableiten, als auch wieder einen Automaten mit nur einem einzigen Zustand erzeugen kann, der die von der Grammatik erzeugte Sprache mittels leerem Keller akzeptiert.

Ich wollte das zwar in einen meiner Beiträge verwursteln, aber ich bin gerade derart begeistert, dass ich das unbedingt loswerden muss. Vor ein paar Stunden bin ich über ein Programm gestolpert. Es kann natürlich sein, dass die halbe Welt das schon kennt und ich mich hier als Unwissender zum Affen mache, aber das Risiko gehe ich ein!

JFLAP!

Mit dem Ding kann Push Down, Mealy, Moore-Automaten, Turingmaschinen, Grammatiken, etc. simulieren und so prüfen ob die erstellte Maschine auch das gewünschte tut. Alles in Java.

Wow. Ich bin dann erstmal für die nächsten Tage beschäftigt

Update: Flüchtigkeitsfehler rausgenommen.

Das ist nun die letzte Kurseinheit der theoretischen Informatik B. Traurig?

In dieser Kurseinheit geht es um kontextfreie Sprachen (also Sprachen, die Typ-2 und -3 erzeugen). Am besten man betrachtet die letzten drei Kurseinheiten gemeinsam, ggf. erstelle ich eine kleine Zusammenfassung der Kernaussagen bei Gelegenheit um aus den Puzzleteilen wenigstens teilweise ein Gesamtbild zu bekommen.

Lernziel 1

Wann ist eine Grammatik in Chomsky-Normalform und wie konstruiert man eine solche aus einer beliebigen kontextfreien Grammatik?

Zunächst geht es um die Eliminierung von $\epsilon$-Regeln. Unserem leeren Wort, welches als Abschluss einer Ableitung fungiert, indem man ein Nonterminal durch $\epsilon$ ersetzt. D.h. was wir wollen, ist es die $\epsilon$-Regeln (z.B. $A\rightarrow\epsilon$) loszuwerden um eine "effektive" Notation zu bekommen. Aber der Reihe nach:

Chomsky Normalform:

Eine Chomsky Normalform liegt dann vor, wenn alle Regeln/Produktionen die Form $(A\rightarrow a)$ oder $(A\rightarrow BC)$ besitzen mit $A,B,C\in\Pi$ und $a\in\Sigma$.

D.h. wir dürfen hier keine $\epsilon$-Regeln haben und die rechte Seite der Produktion darf entweder nur aus einem Symbol (noch aus mehreren) aus unserem Alphabet oder aus einer Kombination von maximal zwei Nonterminalen bestehen.

Die Frage ist: wie kommen wir von einer kontextfreien Grammatik zu einer in Chomsky Normalform? Ich finde, dass so etwas am besten an einem Beispiel (aus dem Buch von Dirk W. Hoffmann) gezeigt wird.

Beispiel: Grammatik $G$ mit Regelmenge

$S\rightarrow AB$

$S\rightarrow ABA$

$A\rightarrow aA$

$A\rightarrow a$

$B\rightarrow Bb$

$B\rightarrow\epsilon$

1. Elimination der $\epsilon$-Regeln

Hier entfernen wir zunächst alle Regeln der Form $A\rightarrow\epsilon$. Wir man sehen kann, wird das Nonterminal $B$ in unseren regeln durch $\epsilon$ ersetzt. Diese Ersetzung können wir durch Hinzufügen neuer Regeln "vorwegnehmen".

$S\rightarrow AB$

$S\rightarrow A$

$S\rightarrow ABA$

$S\rightarrow AA$

$A\rightarrow aA$

$A\rightarrow a$

$B\rightarrow Bb$

$B\rightarrow b$

Hätten wir z.B. mit der initialen Regelmenge die Ableitungssequenz $S\Rightarrow ABA\Rightarrow AA$ (Regel 2, Regel 6), so haben wir nun nur noch die Sequenz: $S\Rightarrow AA$ (Regel 4). Die Ersetzung von $B$ durch $\epsilon$ wurde durch neue Regeln obsolet und wir sind der Chomsky Normalform, wo eben $\epsilon$ kein Teil der Sprache ist, ein Schritt näher.

2. Elimination von Kettenregeln

Nun kümmern wir uns um die Kettenregeln. Regeln, die von einem Nonterminal auf ein Nonterminal ($S\rightarrow A\rightarrow a$) zeigen sind ebenfalls unnötig. Wir gehen vor wie in Schritt eins.

$S\rightarrow AB$

$S\rightarrow aA$

$S\rightarrow a$

$S\rightarrow ABA$

$S\rightarrow AA$

$A\rightarrow aA$

$A\rightarrow a$

$B\rightarrow Bb$

$B\rightarrow b$

3. Separation von Terminalzeichen

Jetzt sind die Terminalzeichen dran. Wir brauchen auf der rechten Seite nur Zweier-Kombinationen aus Nonterminalen oder ein einzelnes Terminal. Wir ersetzen also z.B. $aA$ durch $\Pi_a A$, wobei $\Pi_a$ ein neues Nonterminal ist, welches mit einer neuen Regel auf $a$ zeigt. Aus $S\rightarrow aA$ wird also $S\rightarrow\Pi_a A$ und $\Pi_a\rightarrow a$.

$S\rightarrow AB$

$S\rightarrow \Pi_aA$

$S\rightarrow a$

$S\rightarrow ABA$

$S\rightarrow AA$

$A\rightarrow \Pi_aA$

$A\rightarrow a$

$B\rightarrow B\Pi_b$

$B\rightarrow b$

$\Pi_b\rightarrow b$

$\Pi_a\rightarrow a$

4. Elimination der Nonterminalketten

Letzter Schritt: zu lange Nonterminalketten auf die Maximallänge von $2$ verkleinern. Das Vorgehen kennt ihr ja schon, es wird einfach eine neue Zwischenregel eingefügt. Aus $S\rightarrow ABA$ werden also $S\rightarrow S_{2}A$ und $S_2\rightarrow AB$:

$S\rightarrow AB$

$S\rightarrow \Pi_aA$

$S\rightarrow a$

$S\rightarrow S_{2}A$

$S_2\rightarrow AB$

$S\rightarrow AA$

$A\rightarrow \Pi_aA$

$A\rightarrow a$

$B\rightarrow B\Pi_b$

$B\rightarrow b$

$\Pi_b\rightarrow b$

$\Pi_a\rightarrow a$

Fertig! Aus eindeutigen Grammatiken lassen sich auch eindeutige Chomsky-Grammatiken erstellen.

Vorteile? Jedes Wort $\omega$ mit $\mid\omega\mid=n$ braucht $2n-1$ Ableitungsschritte, da jeder Ableitungsbaum (bis auf die letzte Ebene) für die Chomsky-Normalform ein Binärbaum ist und wg. $n$ Blättern genau $n-1$ innere Knoten hat!

(Weiterhin im Skript wurde die Greifach-Normalform angesprochen. Ebenso eine reduzierte Grammatik. Die reiche ich später nach, da sie nicht Teil der Lernziele sind.)

Antwort zum Lernziel: Eine Grammatik ist in Chomsky Normalform wenn alle Regeln/Produktionen die Form $(A\rightarrow a)$ oder $(A\rightarrow BC)$ besitzen mit $A,B,C\in\Pi$ und $a\in\Sigma$ ist. Aus einer beliebigen kontextfreien Grammatik lässt sich eine Chomsky Normalform-Grammatik erstellen indem man die $\epsilon$- und Kettenregeln eliminiert, die Terminalzeichen separiert und die Nonterminalketten mit mehr als drei Nonterminalen mittels Zwischenregeln auf maximal zwei Nonterminale verkürzt.

Lernziel 2

Was besagt das Pumping-Lemma für kontextfreie Sprachen und wie wendet man es an?

Wie in dem letzten Beitrag zu KE6 angedroht, gibt es auch ein Pumping-Lemma für kontextfreie Sprachen. Wir erinnern uns: mit dem Pumping-Lemma können wir ein Teilwort $v$, der Zerlegung $uvw$  eines Wortes $\omega$ durch einen Zyklus im endlichen Automaten beliebig aufpumpen. Jedes Wort einer (unendlichen) regulären Sprache verfügt ab einer bestimmten Wortlänge über diese Eigenschaft. Bei endlichen Wortlängen können wir es uns einfacher machen, indem wir für jedes Wort einen akzeptierenden Zustand definieren und Zack! ist die Sprache regulär. Das ist der Grund warum alle endlichen Sprachen regulär sind.

Kümmern wir uns nun um das Pumping-Lemma für kontextfreie Sprachen (nicht vergessen: auch reguläre Sprachen sind kontextfrei, aber nicht alle kontextfreien Sprachen sind regulär - reguläre Sprachen sind eine echte Teilmenge der kontextfreien Sprachen). Ich schreibe die Definition (wieder aus dem Buch von Dirk W. Hoffmann) einfach mal hin und dann schauen wir sie uns genauer an:

Für jede kontextfreie Sprache $L$ existiert ein $j\in\mathbb{N}$, so dass sich alle Wörter $\omega\in L$ mit $\mid\omega\mid\geq j$ in der folgenden Form darstellen lassen:

$\omega=uvwxy$ mit $\mid vx\mid\geq 1$ und $\mid vwx\mid\leq j$.

Mit $\omega$ ist auch $uv^{j}wx^{j}y$ für alle $j\in\mathbb{N}_0$ in $L$ enthalten.

Alle Wörter ab einer gewissen Länge $j$ (unsere Pumping Zahl) enthalten Teilwörter $v$ und $x$, die sich aufpumpen lassen und eines davon ist nicht leer ($\mid vx\mid\geq 1$). Seht Ihr den Unterschied zum Pumping Lemma für reguläre Sprachen? Dort haben wir gefordert, dass wir in der Zerlegung $uvw$ nur $v$ beliebig aufpumpen können. Hier müssen es $v$ und $x$ sein. Das liegt an der evtl. fehlenden rechtslinearen Struktur der Ableitungsbäume, die nur reguläre Sprachen inne haben. Im Beispiel weiter unten wird das gleich deutlicher.

Achtung: um zu zeigen, dass eine Sprache kontextfrei ist, müssen wir nur eine kontextfreie Grammatik die sie erzeugt oder einen Kellerautomaten (kommt im nächsten Beitrag) angeben, der sie erkennt. Das Pumping Lemma ist aber dazu gedacht eine Sprache als nicht kontextfrei zu erkennen (was leider auch nicht immer klappt, dazu gleich mehr).

Erklärung

Wir haben schon massive Vorarbeit geleistet und den Ableitungsbaum einer kontextfreien Sprache in Chomsky-Normalform als binären Baum entlarvt. Seine Eigenschaften erlauben es uns einige Eigenschaften für ein Wort abzuleiten, dass wir für das Pumping Lemma brauchen. Nehmen wir zunächst eine Grammatik $G=(\Pi,\Sigma,R,S)$ in Chomsky Normalform. Durch diese Normalform hat der Baum im Inneren die Form eines Binärbaums mit $2 ^{\mid\Pi\mid}$ Blättern. Wir können also einen Pfad wählen, der min. die Länge $\mid\Pi\mid$ aufweist. Mit dem Startsymbol zusammen haben wir auf dem Pfad min. $\mid\Pi\mid +1$ Nonterminale, so dass eines davon mehrfach aufgetaucht sein muss (erinnert Ihr euch? Unser Zyklus im Automaten!).

Zur Erinnerung: Das $j$ ist unsere Pumping Zahl. Jeder Ableitungsschritt ist ein durchlaufener Zustand in der Maschine, so dass wir bei einer unendlichen Länge an Worten irgendwann durch einen Zyklus bei der Erzeugung eines Wortes laufen müssen. Im Ableitungsbaum haben wir somit tatsächlich mehrmals ein Nonterminal stehen. Nennen wir das Nonterminal einfach mal $A$ und unterteilen das Wort in $uvwxy$.

Um also aus dem Nonterminal $A$ noch einmal ein $A$ herzustellen, muss min. ein Ableitungsschritt $A\rightarrow BC$ durchlaufen werden. D.h. eines der Segmente $v$ oder $x$ hat min. ein Terminal drin. Das folgt aufgrund der Regelstruktur in der Chomsky Normalform.

Wie $u$ oder $w$ aussehen, haben wir keine Ahnung. Macht aber nichts, denn aufgrund dem Doppelvorkommen von $A$ können wir die Teilworte $v$ und $x$ aufpumpen und beliebige Worte der Form $uv^{i}wx^{i}y$ erzeugen indem wir die Ableitungssequenz, ausgehend von unserem Nonterminal $A$ mehrfach für das Mittelstück wiederholen.

Dabei wird jedoch nicht nur ein Teil (wie beim Pumping-Lemma für reguläre Sprachen) wiederholt, sondern zwei.

Ein Beispiel wäre wohl sinnig, oder?

Beispiel: $L_1=\{\{ab\}^n\mid n\in\mathbb{N}\}\Rightarrow(abababab...)$

Die Sprache besteht aus einer unendlichen Kombination aus $ab$ und ist sogar regulär, d.h. wir hätten darauf auch das Pumping-Lemma für reguläre Sprachen anwenden können. Da reguläre Sprachen aber auch kontextfrei sind (und ich zu faul bin mir was neues auszudenken), klappt das Pumping Lemma für kontextfreie Sprachen hier auch.

Wir suchen also eine Zerlegung $uvwxy$, so dass gilt $uv^{i}wx^{i}y\in L_1$, mit $i\in\mathbb{N}_0$ wobei $u$ und $y$ ruhig leer sein dürfen. Außerdem muss gelten $\mid vx\mid\geq 1$ und $\mid vwx\mid\leq j$.

Dazu brauchen wir unsere Pumping Zahl $j$, die als Mindestlänge für das Wort fungiert. Wollen wir einfach mal $j=10$ nehmen. Unser Wort der Länge $10$ sieht also wie folgt aus: $ababababab$. Wir zerlegen das willkürlich (jede andere Zerlegung, die die Voraussetzungen erfüllt ist möglich) in $u=ab,v=ab,w=ab,x=ab,y=ab$ und prüfen ob die oben genannten Voraussetzungen gelten:

$\mid abab\mid = 4\geq 1$ (passt) und

$\mid ababab\mid = 6\leq 10$ (passt auch)

Muss auch nur noch (ich klammere für Übersichtlichkeit aus)

$\{ab\} \{ab\}^{i}\{ab\}\{ ab\}^{i}\{ab\}\in L_1$ mit $i\in\mathbb{N}_0$

gelten. Aber das prüfen wir zuletzt.

Eine Regelmenge in Chomsky Normalform, die diese Sprache erzeugt wäre z.B. die folgende:

$S\rightarrow\Pi_a B$

$B\rightarrow\Pi_b C$

$B\rightarrow C$

$C\rightarrow\Pi_a B$

$\Pi_a\rightarrow a$

$\Pi_b\rightarrow b$

Es ist zwar nicht notwendig sie anzugeben, aber ich würde euch gerne den Ableitungsbaum für das zu zerlegende Wort $ababababab$ zeigen. Das verdeutlicht das Lemma etwas besser.

Mal nebenbei: aus diesem Grund werden reguläre Grammatiken auch rechtslineare Grammatiken genannt: der Baum kippt, wie Ihr sehen könnt, nach rechts weg. Das ist der Grund, warum wir im Pumping Lemma für reguläre Sprachen nicht zwei, sondern nur ein Teilwort aufpumpen müssen.

Es ist leicht einzusehen, dass wir hier bereits ab $u$ einen Zyklus haben, der sich bis $y$ durchzieht. $u$ und $y$ könnten aber auch leer sein, wäre für unser Lemma egal. Wichtig ist, dass wir $v$ und $x$ wie im Lemma gefordert aufpumpen können und das Wort immer noch in $L_1$ liegt.

Und was würde passieren wenn wir $v$ oder $x$ entfernen ($i=0$) oder beliebig aufpumpen ($i\geq0$) um die letzte Voraussetzung $ab ab^{i}ab ab^{i} ab\in L_1$ mit $i\in\mathbb{N}_0$ zu erfüllen? Probieren wir das mal aus (ich klammere $uvwxy$ der Übersichtlichkeit halber aus):

$i=0\Rightarrow\{ab\}\{\}\{ab\}\{\}\{ab\}$

$i=1\Rightarrow\{ab\}\{ab\}\{ab\}\{ab\}\{ab\}$

$i=2\Rightarrow\{ab\}\{abab\}\{ab\}\{abab\}\{ab\}$

$...$

Und? Sind die Worte in $L_1$? Ja, sie sind es. Damit ist die Sprache kontextfrei.

Wichtig: meine der Faulheit geschuldete Wahl einer regulären Sprache als Beispiel ist aufgrund der rechtslinearen Struktur des Baumes vielleicht nicht optimal gewesen, denn genau das macht - wie eiter oben erwähnt - den Unterschied zwischen den beidem Lemmata aus.

Während bei einer regulären Sprache der Ableitungsbaum nach rechts kippt und wir nur das $v$, d.h. den rechten Teilbaum in der Zerlegung $uvw$ betrachten müssten, so könnte bei einer kontextfreien (aber nicht regulären und damit auch nicht rechtslinearen) Sprache der Ableitungsbaum gleichzeitig nach links und rechts aufspannen. Das ist der Grund, warum wir den Baum nicht in drei, sondern in fünf Teile zerlegen (nämlich $uvwxy$) und beide Äste, links und rechts, mit $v$ und $x$ betrachten müssen.

Denn bei den regulären Sprachen wird mit $v$ nur der rechte Teilbaum aufgepumpt (wir haben ja aufgrund der rechtslinearen Struktur der regulären Sprachen keinen anderen), während es bei den kontextfreien (aber nicht unbedingt regulären) Sprachen möglich sein muss beide Teilbäume $v$ und $x$ verlängern zu können. Soweit klar? Evtl. reiche ich ein anderes Beispiel nach um es zu verdeutlichen.

Lust auf ein Negativbeispiel?

Beispiel: $L_2=\{a^n b^n c^n\mid n\in\mathbb{N}\}\Rightarrow(abc,aabbcc,...)$

Auch hier suchen wir einer Zerlegung $uvwxy$ mit den oben genannten Eigenschaften:

$\mid vx\mid\geq 1$,

$\mid vwx\mid\leq j$ und

$uv^{i}wx^{i}y\in L_2$, mit $i\in\mathbb{N}_0$

Wir brauchen wieder unsere Pumping Zahl $j$, aber zunächst schauen wir uns die Worte doch einmal an für $n\leq3$:

$n=1\Rightarrow abc$

$n=2\Rightarrow aabbcc$

$n=3\Rightarrow aaabbbccc$

Fällt euch schon etwas auf? Versucht doch einmal eine Zerlegung $vwx$ (denn $u$ und $y$ dürfen ja ruhig leer sein) z.B. von $aaabbbccc$ mit den oben genannten Kriterien anzugeben. Ich mache einfach mal ein paar Beispielzerlegungen für das Wort der Länge $6$, d.h. $j=6$:

Während Ihr die ersten beiden Kriterien $\mid vx\mid\geq 1$ und $\mid vwx\mid\leq 6$ noch erfüllen könnt, sieht es mit $uv^{i}wx^{i}y\in L_2$, mit $i\in\mathbb{N}_0$ schon sehr düster aus. Versuchen ($u$ und $y$ bleiben einfach mal leer, die sind uns egal. Ich klammere $vwx$ wieder für die Übersichtlichkeit aus)?

Zerlegung Nr. 1:

$i=0\Rightarrow\{u\}\{\}\{bbb\}\{\}\{y\}\notin L_2$

Bereits mit $i=0$ klappt es nicht. Das erzeugte* Wort ist nicht in unserer untersuchten Sprache. (*was ist das Gegenteil von aufgepumpt? Abgepumpt?)

$i=1\Rightarrow\{u\}\{aaa\}\{bbb\}\{ccc\}\{y\}\in L_2$

Hier geht es noch. Ist aber auch kein Wunder, denn das ist ja unser von Anfang an ausgesuchtes Wort, dass wir zerlegen wollten.

$i=2\Rightarrow\{u\}\{aaaaaa\}\{bbb\}\{cccccc\}\{y\}\notin L_2$

Und ab hier geht es dann nicht mehr weiter. Seht Ihr warum? Wir müssen bei der Erhöhung von $i$ zwei Teile des Wortes verlängern: $v$ und $x$. Dabei bleibt aber ein Teil auf der Strecke, der nicht mit verlängert wird: $w$. Das sind unsere $b's$. Das ist aber Voraussetzung, denn in der Sprache sind nur Worte, die die gleiche Anzahl $a's$ wie $b's$ und $c's$ haben.

Zerlegung Nr. 2:

$i=0\Rightarrow\{u\}\{\}\{abbb\}\{\}\{y\}\notin L_2$

Auch hier: nix.

$i=1\Rightarrow\{u\}\{aa\}\{abbb\}\{ccc\}\{y\}\in L_2$

Wie gerade eben: unser ausgesuchtes Wort, was natürlich funktioniert.

$i=2\Rightarrow\{u\}\{aaaa\}\{abbb\}\{cccccc\}\{y\}\notin L_2$

Wieder eine unterschiedliche Anzahl an $a's$, $b's$ und $c's$. War also wieder nichts.

Zerlegung Nr. 3:

$i=0\Rightarrow\{u\}\{\}\{bbbc\}\{\}\{y\}\notin L_2$

Nope.

$i=1\Rightarrow\{u\}\{aaa\}\{bbbc\}\{cc\}\{y\}\in L_2$

Erneut: unser ausgesuchtes Wort, was wieder funktioniert.

$i=2\Rightarrow\{u\}\{aaaaaa\}\{bbbc\}\{cccc\}\{y\}\notin L_2$

Auch hier: Wieder eine unterschiedliche Anzahl an $a's$, $b's$ und $c's$. Keine Chance.

Ich will euch nicht weiter quälen: Ihr seht, dass es einfach nicht funktioniert, egal welche Pumping Zahl $j$ und welche Zerlegung wir wählen. Während wir zwei Teilworte $v$ und $x$ für das Lemma verlängern müssen, bleibt eine immer auf der Strecke. D.h. die Zusammensetzung der Elemente ist abhängig von Ihrer Umgebung, ihrem Kontext! Damit ist die Sprache $L_2$ nicht kontextfrei, sondern kontextsensitiv.

Etwas will ich euch aber nicht vorenthalten: denn das Pumping Lemma funktioniert nicht immer. Es gibt kontextsensitive Sprachen, die das Lemma dennoch erfüllen! Das Problem liegt in der Startposition der Teilwörter der Zerlegung. Denn dazu macht das Lemma keine Aussage (Prefix $u$ und Suffix $y$ können ja leer sein). Gelingt es uns den kritischen Abschnitt im Wort (in unserem Beispiel war das $w$) irgendwie zu umgehen, so haben wir eine evtl. kontextsensitive Sprache, die unser Pumping Lemma trotzdem erfüllt. Ein Beispiel hierzu ist die Sprache:

$L_3=\{b^k c^l d^m\mid k,l,m\in\mathbb{N}\}\cup\{a^m b^n c^n d^n\mid m,n\in\mathbb{N}\}$

Hier versagt das Pumping Lemma für kontextfreie Sprachen, den $L_3$ erfüllt bei einer geschickten Wahl von $j$ und einer Zerlegung $uvwxy$ alle drei Lemma-Kriterien. Ich möchte hier nicht näher darauf eingehen, da das im Skript nicht behandelt wurde (tue es bei Gelegenheit aber trotzdem wenn etwas Zeit ist). Aber mit Ogdens Lemma kann man diese kontextsensitive Sprache auch als eine solche erkennen!

Antwort zum Lernziel: Das Pumping Lemma für kontextfreie Sprachen besagt, dass es bei einem Wort mit Mindestlänge $j$ eine Zerlegung $uvwxy$ geben muss, die folgende Kriterien erfüllt:

$\mid vx\mid\geq 1$,

$\mid vwx\mid\leq j$ und

$uv^{i}wx^{i}y\in L_2$, mit $i\in\mathbb{N}_0$

Dabei werden die Teilworte $v$ und $x$ beliebig aufgepumpt. Sollte keine Zerlegung diese Kriterien erfüllen, so ist die Sprache auch nicht kontextfrei.

Angewandt wird es, indem man sich zunächst ein Wort aus der zu untersuchenden Sprache sucht und eine Zerlegung angibt, welche die oben genannten Kriterien für alle $i\in\mathbb{N}_0$ erfüllt. Liegt das neue Wort mit den aufgepumpten Teilworten $v$ und $x$ dann nicht in der Sprache, zu der das Ursprungswort gehörte, so ist die Sprache auch nicht kontextfrei.

Es gibt jedoch Sprachen, die nicht kontextfrei sind und das Lemma dennoch erfüllen. Mit Ogdens Lemma kann man diese jedoch als nicht kontextfrei nachweisen.

Das war Teil 1 von 3 der Kurseinheit 7.

Bei Fehlern wieder die große Bitte: ab damit in die Kommentare damit ich das schleunigst berichtigen kann. Vor allem in mathematischen Kursen sind Fehler eine ungemein frustrierende Lernbehinderung, wie ich in Computersysteme 1 und 2 erfahren durfte: da zweifelt man schon tagelang an seinem Rechenweg weil im Skript ein anderes Ergebnis rauskommt. Das ist nervig!

Lernziel 7

Was sind Ableitungsbäume kontextfreier Grammatiken?

Wie wir aus dem Beitrag zu KE5 bereits wissen, sind reguläre Sprachen (Typ-3, rechte Seite einer Regel besteht nur aus einem Terminal, dem ein Nonterminal folgt oder einem leeren Wort) eine echte Teilmenge der kontextfreien Sprachen (Typ-2, linke Seite der Regel besteht nur aus einem Nonterminal). Die Typ-3-Sprachen sind nur noch ein Stück weiter eingeschränkt . Damit sind reguläre Sprachen auch kontextfrei, denn alle Nonterminale können unabhängig von ihrer Umgebung ersetzt werden (im Gegensatz zu Typ-1-Grammatiken, die auch kontextsensitive Regeln erlauben, dort kann die linke Seite der Regel auch aus einem Terminal und einem Nonterminal bestehen. Der Kontext ist also die Verbindung von Terminal und Nonterminal im Wort).

Wenn man nach Ableitungsbäumen und kontextfreien Grammatiken sucht, findet man diesen Beitrag in der Wikipedia und der Fall ist eig. klar. Leider hat das Skript auch noch 4 Seiten zum Thema der Notation für die kontextfreie Grammatik (die polnische Notation und die vereinfachte Notation). Anschließend geht es um die abstrakte Syntax, das Erzeugungssystem, die abstrakte Semantik und dann drei Arten von Ableitungsbäumen. Nun stellt sich mir die Frage, ob ich einfach ein paar Beispiele für den Ableitungsbaum aus dem Artikel bringen oder das Skript sezieren soll. Just in diesem Moment entscheide ich mich für Ersteres in Kombination mit dem Beispiel aus dem Skript.

Zunächst haben wir drei Arten von Ableitungsbäumen:

1. Baum mit Wurzel $a$ und Front $a\in(\Sigma\cup\Pi)$. Das ist ein ein einzelner Knoten $a$, der gleichzeitig auch die Wurzel ist. $a$ kann nur ein Wort über der Menge der Terminale und Nonterminale sein. Die Wurzel ist das ausgehende Zeichen, d.h. das Startsymbol (in diesem Fall ist es nicht die Startregel aus $R$).
2. Baum mit Wurzel $A$ (Nonterminal) und Front $\epsilon$ (leeres Wort) wenn es die folgende Abschlussregel in der Grammatik gibt: $(R\rightarrow\epsilon)$.
3. Und hier endlich der "echte" Baum mit einer Wurzel $A$ und einer Front $\omega$ wenn es eine Ableitungssequenz gibt, so dass man das Wort $\omega$ mittels der Regeln aus der Grammatik ableiten kann.

Bitte macht euch noch einmal klar, dass die Front das abgeleitete Wort (oder Zeichen) ist und die Wurzel das Startsymbol (was nicht unbedingt die Startregel sein muss). Die folgende Abbildung zeigt zwei Bäume (mit grüner Front), die auch im Skript Verwendung finden mittels der Regelmenge:

$S\rightarrow a\mid b\mid\emptyset\mid (S\cup S)\mid (SS)\mid S^{*}$

Beispiel: Ableitung von $\emptyset$ (mittels Baumart Nr. 1)

Sequenz: nicht notwendig, da nur Baumart Nr. 1

Beispiel: Ableitung von $(\emptyset^{*}\cup a)$ (mittels Baumart Nr. 3)

Sequenz: $S\Rightarrow(S\cup S)\Rightarrow(S^{*}\cup S)\Rightarrow(\emptyset^{*}\cup S)\Rightarrow(\emptyset^{*}\cup a)$

Den Baum baut man so sukzessive auf. In der Abbildung sind die einzelnen Ableitungsschritte der Sequenz von $1-5$ nummeriert. Am Ende liest man einfach nur das gesuchte Wort $\omega$ anhand der Blätter (Knoten ohne Kinder) von links nach rechts ab (auch Tiefensuche genannt).

Baumart Nr. 2 kam für ein Beispiel nicht in Frage, da wir das leere Wort $\epsilon$ mangels passender Regel nicht ableiten können (siehe unsere Regelmenge) und ich zu faul war eine neue Regelmenge zu definieren. Evtl. hole ich das noch nach wenn die Zusammenfassungen zu allen Kurseinheiten online sind.

Noch eine Kleinigkeit zur Notation:

Wenn das Wort $\omega$ einen Ableitungsbaum mit Wurzel $A$ und Front $\omega$ hat, so gilt $A\xrightarrow{\text{*}}\omega$

Es könnte auch mehrere Ableitungsbäume für ein Wort geben. Nehmen wir wieder das Beispiel aus dem Skript:

Beispiel: $S\rightarrow SS\mid a\mid b$ und abgeleitetes Wort $aba$

Sequenz 1: $S\Rightarrow SS\Rightarrow SSS\Rightarrow aSS\Rightarrow abS\Rightarrow aba$

Sequenz 2: $S\Rightarrow SS\Rightarrow aS\Rightarrow aSS\Rightarrow abS\Rightarrow aba$

Durch die unterschiedlichen Ableitungssequenzen für ein Wort, haben wir auch unterschiedliche Ableitungsbäume. Damit ist die Grammatik aus diesem Beispiel mehrdeutig.

Antwort zum Lernziel: der Ableitungsbaum bezeichnet die baumförmige Darstellung der Ableitung eines Wort $\omega$ aus einer Grammatik. Sobald der Baum aufgebaut ist, wird das Wort von links nach rechts anhand der Blätter abgelesen (Tiefensuche).

Lernziel 8

Wann ist eine kontextfreie Grammatik bzw. Sprache eindeutig?

Wie wir im letzten Beispiel gesehen haben, kann es zu einen Wort mehrere Ableitungsbäume geben. Diese Grammatiken sind für die Syntaxdefinition von Programmiersprachen aufgrund dieser Mehrdeutigkeit jedoch unbrauchbar. Der Programmtext würde sich so auf verschiedene Weise ableiten lassen. Wir sind also auf eindeutige Grammatiken für Programiersprachen angewiesen.

Eine eindeutige Grammatik ist also dann eindeutig wenn jedes Wort aus der durch die Grammatik definierten Sprache genau einen Ableitungsbaum hat. Ebenso verhält es sich mit der Sprache: sie ist dann eindeutig wenn es eine eindeutige Grammatik gibt, dass die Sprache beschreibt.

Man kann die Mehrdeutigkeit auch durch die Verwendung von Präzedenzregeln eliminieren. Da das nicht Teil des Skripts war, lasse ich das zunächst einmal aus. Wenn mehr Zeit ist, schreibe ich evtl. noch ein paar Zeilen dazu. Bis dahin sei auf ein PDF der Uni Marburg zum Thema verwiesen.

Antwort zum Lernziel: siehe Definition von oben.

Ausgelassen habe ich hier die abstrakten Syntaxbäume, da sie nicht in den Lernzielen erwähnt werden. Aber vielleicht der Vollständigkeit halber noch ein paar Worte zum Thema: Was ist also diese abstrakte Syntax?

Sie ist nichts anderes als die wesentlichen Teile des Ableitungsbaumes zu einem Ausdruck. Genau dieser Syntaxbaum wird auch vom Compiler verwendet um den Programmcode zu interpretieren, da der Ableitungsbaum (auch "konkreter Syntaxbaum" statt Ableitungsbaum genannt) zu viele Informationen beinhaltet, die unwichtig sind. Die Informationen können auch in in anderer Form gespeichert werden.

Dazu bemühe ich wieder das Beispiel aus dem Skript mit der Regelmenge

$S\rightarrow a\mid b\mid\emptyset\mid (S\cup S)\mid (SS)\mid S^{*}$

aus der verwendeten (eindeutigen) Grammatik.

Beispiel: abgeleiteter Ausdruck $(((aa)b)^{*}\cup(b\cup\emptyset^{*}))$

Sequenz: $S\Rightarrow(S\cup S)\Rightarrow(S^{*}\cup (S\cup S))\Rightarrow((SS)^{*}\cup (b\cup S^{*}))\Rightarrow((SS)b^{*}\cup (b\cup\emptyset^{*}))\Rightarrow((aa)b^{*}\cup (b\cup\emptyset^{*}))$

Die folgende Abbildung zeigt den zugehörigen Ableitungsbaum (konkreter Syntaxbaum):

Für uns spannend sind aber nicht die konkreten Ableitungsinformationen, sondern einfach nur die abstrakte Syntax. Entfernen wir nun alle unnötigen Knoten aus dem Ableitungsbaum (konkreter Syntaxbaum), so bekommen wir unseren sehr kompakten abstrakten Syntaxbaum.

Wie man sich leicht vorstellen kann, kann dieser Baum deutlich einfacher gespeichert und geparsed werden als sein großer Bruder.

Eine schöne Darstellung findet sich auch in einigen Folien aus Magdeburg. Im Kurs 1810 (Compilerbau) der FernUni wird verstärkt darauf Bezug genommen. Wer sich diesen Kurs im Studium als Modul anhören möchte (ist im Katalog B), sollte sich diese Bäumchen evtl. genauer ansehen.

Damit haben wir auch KE6 hinter uns. Bei Fehler gilt wie immer: so schnell wie möglich in die Kommentare.