Update 3: Korrektur der Beweisidee für Durchschnitt, nicht Vereinigung. Danke Phil.

Update 2: Korrektur Aufgabe aus Lernziel 3. Danke Mike.

Update: Aufgabe mit Lösung hinzugefügt um aus einem Automaten eine Regelmenge abzuleiten.

Ohne viele Worte: weiter in KE6.

Lernziel 3

Wie konstruiert man zu einem endlichen Automaten $A$ einen regulären Ausdruck $\alpha$ mit $L(A)=L(\alpha)$?

Hier kommt einiges an Schreibarbeit auf uns zu. Wie wir aus dem Beitrag zu KE5 wissen, können wir reguläre Sprachen mit einem regulären Ausdruck beschreiben. Um zu beweisen, dass eine Sprache regulär ist, muss man sie auf eine reguläre Grammatik, einen endlichen Automaten, einen regulären Ausdruck oder auf bereits bekannte reguläre Sprachen zurückführen.

Hier haben wir einen Automaten $A$ zu einer Sprache $L$ bereits gegeben (die Sprache ist also als regulär bewiesen) und suchen nun auch noch einen regulären Ausdruck, der uns dieselbe Sprache beschreibt. Wir verwenden als beispiel wieder den Automaten $A$ aus dem vorherigen Beitrag:

Beispiel: $A=(\{a,b\},\{0,1,2\},0,2,\delta)$ mit

$\delta=\{(1,a,1),(1,b,1),(1,a,2),(2,b,3),(3,a,3),(3,b,3)\}$

Hier nochmal der Graph damit Ihr nicht zwischen den Beiträgen wechseln müsst:

Der Ansatz im Beweis ist ein geringfügig anderer, ich will sagen etwas formaler aus die Vorgehensweise, die ich gleich vorstelle. Das Ergebnis ist aber dasselbe. Wenn jemand eine schöne Erklärung für den formalen Beweis im Skript hat, der die folgenden zwei Formeln verwendet, immer her damit.

${L_{ij}}^{0}=\{a\in\Sigma\mid (i,a,j)\in\delta\}$

${L_{ij}}^{k}={L_{ij}}^{k-1}\cup{L_{ik}}^{k-1}\cdot({L_{kk}}^{k-1})^*\cdot{L_{kj}}^{k-1}$

Wir machen das etwas weniger formal. Die Schritte sind wie folgt:

Wir führen einen neuen Startzustand $S$ ein, der mit einem leeren Wort $\epsilon$ bereits in unseren ehemaligen Startzustand übergeht. Ebenfalls wird ein neuer Endzustand $E$ eingesetzt, zu dem ein Pfeil von jedem ehemaligen Endzustand gezogen wird. Auch hier wird das leere Wort als Übergang verwendet. Unser neuer Graph sieht wie folgt aus:

Wenn wir uns den Übergang von Zustand $0$ zu Zustand $1$ anschauen, fällt auf, dass wir in jedem Fall ein $a$ als Abschluss der Zeichenkette brauchen um zu Zustand $1$ zu kommen. Beliebig lange Worte, die aus $a$ oder $b$ zusammengesetzt sind, spielen für den Übergang aufgrund der Schleife im Zustand $0$ keine Rolle solange das $a$ als Suffix im Wort vorhanden ist. Das führt uns auch zu den beiden Überführungsregeln, die wir brauchen. Ein Bild sagt mehr als tausend Worte:

Klammern wir die Ausdrücke bei Regel 1, wird es evtl. deutlicher: $\{x\}\cdot\{y\}^*\cdot\{z\}$ ist dann der gesuchte, reguläre Ausdruck um von Zustand $A$ zu Zustand $C$ zu kommen nachdem man Zustand $B$ entfernt hat. Ein Wort, dass den regulären Ausdruck erfüllen würde, wäre z.B. $xyyyyyyyz$ oder $xz$. Eines, dass ihn nicht erfüllt ist $xy$.

Regel 2 ist noch einfacher: Von Zustand $A$ zu Zustand $C$ kommt man durch die Konkatenation von $x$ und $z$. That's it.

Das alles angewendet auf unseren Graphen führt uns zu folgendem:

Die leeren Worte $\epsilon$ brauchen wir nun nicht mehr und können sie streichen. Korrekt geklammert haben wir den gesuchten, regulären Ausdruck $\alpha=\{a,b\}^{*}\cdot\{ab\}\cdot\{a,b\}^{*}$ und damit gilt: $L(A) = L(\alpha)$. Wir können auch problemlos eine reguläre Grammatik $G$ zum Automaten $A$ angeben um $L(A) = L(\alpha) = L(G)$ zu bekommen. Könnt Ihr mal selbst probieren.

Aufgabe: findet zum Automaten $A$ die Regelmenge der passenden Grammatik

Lösung zeigen

Lernziel 4

Wie zeigt man, dass die regulären Sprache unter den in Satz 8.4.1 genannten Operationen abgeschlossen sind (Beweisidee)?

Was waren nochmal die Operationen in Satz 8.4.1? Ach ja:

• Vereinigung, Komplexprodukt, Stern
• Durchschnitt, Mengendifferenz, Komplement
• Spiegelung

Und was Abgeschlossenheit ist, wisst Ihr doch noch, oder? Die Anwendung der Operationen auf zwei Mengen der selben Klasse führt nicht aus dieser Klasse heraus. Ein einleuchtendes Beispiel sind die ganzen Zahlen $\mathbb{Z}$, die bzgl. Subtraktion, Addition und Multiplikation abgeschlossen sind. Aber nicht bzgl. der Division: $1:3=\frac{1}{3}$ und es gilt $\frac{1}{3}\in\mathbb{Q}$ und $\frac{1}{3}\notin\mathbb{Z}$.

Wie beweisen wir denn nun, dass die regulären Sprachen bzgl. der Operationen abgeschlossen sind? Fangen wir mit dem Komplement an:

Beweisidee zur Abgeschlossenheit bzgl. des Komplements

$B\setminus A=\{x\in B\mid x\notin A\}$, wobei $B\subseteq A$

Was müssen wir zeigen? Es muss gelten $L(A)=L$ und $L(\overline{A})=\Sigma^{*}\setminus L=\overline{L}$. D.h. in $\overline{L}$ liegen alle Worte aus $\Sigma^{*}$, die nicht in $L$ liegen. Das wäre dann unser Komplement.

Es werden zwei vollständige und determinierte Automaten $A$ und $\overline{A}$ konstruiert, die sich nur in ihren Endzuständen unterscheiden. Wir erinnern uns, dass ein Wort $x\in\Sigma^{*}$ nur dann zu einer Sprache $L(A)$ gehört, wenn es ausgehend vom Startzustand den Automaten $A$ in einen Endzustand überführt.

Der Unterschied zwischen den Automaten sind nur ihre Endzustände: für Automat $A$ sind die Endzustände in $F$ und für Automat $\overline{A}$ sind die Endzustände in $Q\setminus F$, d.h. alle Zustände außer den Endzuständen $F$ des Automaten $A$. Die Überführungsfunktionen aus $\delta$ bleiben erhalten. Ein kleines Beispiel um es greifbarer zu machen:

Beispiel: Sei $A$ der Automat von oben mit $A=(\{a,b\},\{0,1,2\},0,2,\delta)$, so wäre $\overline{A}$ der andere Automat mit $\overline{A}=(\{a,b\},\{0,1,2\},0,\{0,1\},\delta)$. Beachtet die Endzustände des Automaten $\overline{A}$.

Ist also ein Wort $x\in\Sigma^{*}$ in der Sprache $L$, so führt es die Maschine $A$ in den Endzustand $2$. Ist es nicht in $L$, so sind wir notgedrungen immer noch in Zustand $0$ oder $1$ unterwegs. Und das sind ja genau die Endzustände unserer Maschine $\overline{A}$, was bedeutet, dass wenn ein Wort nicht in Sprache $L$ ist, so ist es gezwungenermaßen in Sprache $\overline{L}$. Die umgekehrte Richtung gilt ebenfalls, wie man sich leicht vorstellen kann.

 Achtung: kontextfreie Grammatiken (Typ-2) sind nicht abgeschlossen bzgl. des Komplement!

Beweisidee zur Abgeschlossenheit bzgl. Vereinigung, Produkt und Stern:

Diese sind bereits nach der Definition der regulären Mengen ebenfalls regulär. Hier müssen wir also nichts mehr tun. Im Skript ist noch eine Beweisidee für die Vereinigung drin, aber vielleicht macht es Sinn diese hier anhand von Beispielen (aus dem Buch von Dirk W. Hoffmann) zu illustrieren.

Beispiel: Nehmen wir zunächst zwei Grammatiken (wir sind wieder bei Grammatiken, nicht mehr bei Automaten) über einem Alphabet $\Sigma$.

$G_1=\{\Pi_1,\Sigma,R_1,S_1\}$ (zur Erinnerung: Nonterminale,  Alphabet, Regeln, Start) mit den Regeln

$S_1\rightarrow A_1 B_1$

$A_1\rightarrow ab\mid aA_{1}b$

$B_1\rightarrow c\mid cB_1$

$G_2=\{\Pi_2,\Sigma,R_2,S_2\}$ mit den Regeln

$S_2\rightarrow A_2 B_2$

$A_1\rightarrow a\mid aA_2$

$B_1\rightarrow bc\mid bB_{2}c$

Wichtig: Wie Ihr unschwer erkennen könnt, sind die Grammatiken nur kontextfrei (Typ-2) und nicht regulär. Das ist jedoch für die Beispiele zur Vereinigung, Produkt und Stern nicht schlimm, dafür sind sie abgeschlossen. Sie sind jedoch nicht abgeschlossen für Durchschnitt und Komplement.

Wir gehen davon aus, dass die Nonterminalmengen $\Pi_1$ und $\Pi_2$ keine gemeinsamen Mengen haben.

Vereinigung

Wir müssen also eine Grammatik erzeugen, die uns $L(G_1)\cup L(G_2)$ erzeugt. Dazu werden die Mengen $\Pi_1$ und $\Pi_2$ (Nonterminale), sowie $R_1$ und $R_2$ (Regeln) zu neuen Mengen zusammengefasst. Auch kümmern wir uns um das Startsymbol, welches beide Startsymbole $S_1$ und $S_2$ zusammenfasst. Auch müssen wir eine neue Produktion einführen und wir erhalten:

$G_{1\cup 2}=\{\Pi_1\cup\Pi_2,\Sigma,R_1\cup R_2\cup\{S\rightarrow S_1\mid S_2\},S\}$

Die Regelmenge sieht im Ergebnis wie folgt aus:

$S\rightarrow S_1\mid S_2$

$S_1\rightarrow A_1\mid B_1$

$A_1\rightarrow ab\mid aA_{1}b$

$B_1\rightarrow c\mid cB_1$

$S_2\rightarrow A_{2}B_2$

$A_2\rightarrow a\mid aA_2$

$B_2\rightarrow bc\mid bB_{2}c$

Und diese Grammatik erzeugt uns $L(G_1)\cup L(G_2)$. Sie ist zwar nicht regulär, aber wir können sie durch Einführung von neuen Regeln und Zuständen zu einer regulären Grammatik transformieren.

Die Beweisidee für den Durchschnitt sollten wir aber auch nicht unerwähnt lassen: Ausgehend von zwei Automaten, die unsere Mengen $L$ und $M$ berechnen, werden weitere Automaten für $\overline{L}$ und $\overline{M}$ erzeugt. Zu diesen Mengen werden zwei reguläre Ausdrücke $\alpha$ und $\beta$ konstruiert und diese mittels $\cup$ zu $(\alpha\cup\beta)$ verbunden, was nichts anderes als ${L}\cap{M}$ ist.

Zu diesem Ausdruck wird eine Grammatik $G$ konstruiert, zur Grammatik ein vollständiger Automat $C$, welcher anschließend zu $\overline{C}$ umgeformt wird. Alles zusammengenommen ist dann $L(\overline{C})=\overline{L(C)}=\overline{\overline{L}\cup\overline{M}}=L\cap M$. Ich fand die Darstellung aus dem Buch von Dirk. W. Hoffmann mit dem Beispiel einfacher nachzuvollziehen.

Komplexprodukt

Hier brauchen wir eine Grammatik für $L(G_1)L(G_2)$. Dazu werden wieder die Nonterminale und Regeln zusammengeführt und die Startsymbole durch ein neues ersetzt.

$G_{1\cdot 2}=\{\Pi_1\cup\Pi_2,\Sigma,R_1\cup R_2\cup\{S\rightarrow S_{1}S_2\},S\}$

Und das ist unsere neue Regelmenge:

$S\rightarrow S_{1}S_2$

$S_1\rightarrow A_1B_1$

$A_1\rightarrow ab\mid aA_{1}b$

$B_1\rightarrow c\mid cB_1$

$S_2\rightarrow A_{2}B_2$

$A_2\rightarrow a\mid aA_2$

$B_2\rightarrow bc\mid bB_{2}c$

Auch das sieht gut aus. Nun zum Stern.

Sternoperator: Kleene'sche Hülle

Was brauchen wir? $L(G_1)^{*}$! Wir brauchen hierzu einfach nur neue Ableitungsregeln, die es uns ermöglichen aus dem neuen Startsymbol eine beliebige Anzahl des ursprünglichen Startsymbols zu erzeugen. Die neue Grammatik sieht wie folgt aus:

$G_{1^{*}}=\{\Pi_1,\Sigma,R_1\cup\{S\rightarrow\epsilon\mid SS_1\},S\}$

Und das ist unsere neue Regelmenge:

$S\rightarrow \epsilon\mid SS_{1}$

$S_1\rightarrow A_1B_1$

$A_1\rightarrow ab\mid aA_{1}b$

$B_1\rightarrow c\mid cB_1$

Und fertig!

Weiter geht es mit dem Durchschnitt für reguläre Sprachen.

 Beweisidee zur Abgeschlossenheit bzgl. des Durchschnitts:

$B\cap A=\{x\in B\mid x\in A\}$

Mittels der de Morgan'schen Regel gilt: $L\cap M = \overline{\overline{L}\cup\overline{M}}$. Und die Vereinigung haben wir ja bereits in der Definition als regulär drin.

 Achtung: kontextfreie Grammatiken (Typ-2) sind nicht abgeschlossen bzgl. des Durchschnitts!

Beweisidee zur Abgeschlossenheit bzgl. der Differenz

$B\setminus A=\{x\in B\mid x\notin A\}$, wobei hier $B$ nicht unbedingt eine Teilmenge von $A$ sein muss.

Es gilt: $L\setminus M=L\cap\overline{M}$

Achtung: kontextfreie Grammatiken (Typ-2) sind nicht abgeschlossen bzgl. des Durchschnitts und somit auch nicht bzgl. der Differenz!

Beweisidee zur Abgeschlossenheit bzgl. der Spiegelung

Es muss also gelten $L$ ist regulär $\Rightarrow L^R = \{a_n,...,a_1\mid a_1,...,a_n\}$ ist regulär.

Ich finde hier den Beweis mittels Automat einfacher. Dazu wird einfach ein neuer Automat, der Umkehrautomat wie folgt gebildet:

• $(b,x,a)$ gdw. $(a,x,b)$ (Umkehrung der Zustandsübergänge)
• Startzustand $q_0$ wird zum neuen Endzustand
• Neuer Startzustand mit $\epsilon$-Übergängen zu allen alten Endzuständen

Damit haben wir unser gespiegeltes Wort. Und da sich ansonsten nichts am Automaten geändert hat, ist die Ergebnismenge weiterhin regulär.

Antwort zum Lernziel: man zeigt die Abgeschlossenheit der regulären Sprachen bzgl. der Operationen, indem man Automaten erstellt, die die Operationen auf den beiden Mengen durchführen. Nach Definition aus dem Beitrag zu KE5 sind die regulären Sprachen, auf denen die Operationen $\cup$, $\cdot$ und $*$ ausgeführt werden ebenfalls regulär. Können wir also die oben genannten Operationen damit "nachbilden", ist uns der Nachweis gelungen (siehe Beweis zum Durchschnitt).

Lernziel 5

Welche "Probleme" sind für reguläre Sprachen entscheidbar?

Der Abschnitt ist kurz, aber wichtig! Es gibt bestimmte Probleme auf den regulären Mengen, die entscheidbar sind. Dazu gehören:

$x\in L_1$? (Sprachproblem, gehört das Wort $x$ zur Sprache $L_1$?)

$L_1\subseteq L_2$? (Inkklusionsproblem, ist $L_1$ eine Teilmenge der Sprache $L_2$?)

$L_1=L_2$? (Äquivalenzproblem, ist die Sprache $L_1$ äquivalent zur Sprache $L_2$?)

$L_1=\emptyset$? (Leerheitsproblem, ist die Sprache $L_1$ leer?)

$L_1$ endlich? (Endlichkeitsproblem, ist die Sprache $L_1$ endlich? D.h. $\#L_1\leq\infty$)

Für Typ-2-Sprachen können wir z.B. das Äquivalenzproblem nicht entscheiden.

Antwort zum Lernziel: Das Sprachproblem, das Inklusionsproblem, das Äquivalenzproblem, das Leerheitsproblem und das Endlichkeitsproblem sind für reguläre Sprachen entscheidbar.

Lernziel 6

Wie lautet das Pumping-Lemma für reguläre Sprachen? Wie kann man es verwenden um nachzuweisen, dass eine Sprache nicht regulär ist?

Die Definition im Skript lasse ich mal für zuletzt. Erst einmal: mit dem Pumping Lemma für reguläre Sprachen (für Typ-2-Sprachen gibt es auch eins) haben wir ein Werkzeug an der Hand, mit dem wir nachweisen können, dass eine Sprache nicht regulär ist. Das liegt an der festgelegten Struktur der Produktionen (Regeln) unserer Sprachtypen.

Sieht man sich z.B. die festgelegten Regeln für unsere regulären Sprachen an, so sieht man, dass wir in jedem Schritt ein Terminal und ein Nonterminal erzeugen, wobei das Nonterminal immer an letzter Stelle steht. Abgesehen von der Abschlussregel mit dem leeren Wort $\epsilon$ haben wir hier ein festgelegtes Erzeugungsmuster. Das Nonterminal an letzter Stelle begrenzt die Anzahl der Regeln, die im nächsten Schritt anzuwenden sind und erlaubt uns Rückschlüsse auf die bisher erzeugten Zeichen.

Haben wir bei der Erzeugung eines Wortes mehr Schritte getan, als Nonterminale zur Verfügung stehen, so muss min. ein Nonterminal irgendwo mehrfach aufgetaucht sein. Bildlich gesprochen sind wir also über einen Zyklus im Automaten gestolpert. Denn jeder Automat zu einer regulären Sprache hat auch eine endliche Anzahl an Zuständen.

Beispiel: nehmen wir einfach $G_1$ aus dem vorherigen Beitrag: $G_1=(\Pi,\Sigma,R,S)$ mit $\Pi=\{S,B,C\}$, $\Sigma=\{a,b\}$, Startsymbol $S$ und den Regeln $R$:

$S\rightarrow aB$

$B\rightarrow bC$

$C\rightarrow\epsilon\mid aB$

Damit ist $L(G_1)=\{ab\}*$, also alle Worte über $ab$, d.h. z.B. $ab$, $ababab$ oder $ababababa$. Hier habt Ihr auch euren Zyklus. Wir haben z.B. das Wort $abab$: die Anzahl der Terminale ist größer als die Anzahl der Zustände im Automaten. Damit müssen wir min. einen Zyklus durchlaufen haben.

Jetzt ist der richtige Zeitpunkt für die Definition des Pumping Lemma:

Für jede reguläre 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=uvw$ mit $\mid v\mid\geq 1$ und $\mid uv\mid\leq j$

Dann ist mit $\omega$ auch das Wort $uv^{i}w$ für alle $i\in\mathbb{N}_0$ enthalten.

$j$ wird Pumping-Zahl genannt. Wenden wir die Definition von oben also auf unser Beispiel an, so hat das kleinste Wort mit einem Zyklus die Länge $j=4$ ($abab$). Dann muss das Anfangsstück $u$ mindestens die Länge $1$ aufweisen und in Kombination mit dem Mittelteil maximal $4$ Zeichen lang sein. Wichtig ist, dass $j$ nicht die kleinste Länge haben muss, auf die die Kriterien zutreffen. Es genügt irgendein $j$, das passt und man eine Zerlegung $uvw$ für das Wort zeigen kann.

In unserem Beispiel mit dem Wort $$a ba b$ und $j=4$ haben wir eine:

Es lässt sich der Mittelteil $v$ also beliebig oft wiederholen und das daraus entstandene Wort ist immer noch noch in $L$. Ist das nicht der Fall, so ist die Sprache nicht regulär. Wie man oben am Automaten sehen kann, ist die Kombination $ba$ auch genau unser Zyklus! Wir haben in unserem Wort immer ein $a$ am Anfang und ein $b$ am Ende (unsere $u$ und $w$), während wir den Mittelteil $v$ beliebig oft (oder auch gar nicht) wiederholen können.

Kommen wir nun zu einer kleinen Abweichung von der obigen Grammatik.

Beispiel: $G_2=(\Pi,\Sigma,R,S)$ mit $\Pi=\{S,B,C\}$, $\Sigma=\{a,b\}$, Startsymbol $S$ und den Regeln $R$:

$S\rightarrow aB$

$B\rightarrow bC$

$C\rightarrow\epsilon$

Der einzige Unterschied von $G_1$ zu $G_2$ ist, dass der Zustandsübergang von $C$ keinen Zyklus mehr hat. Der Automat sieht nun wie folgt aus:

Die Sprache $L(G_2)$ besteht also nur aus dem Wort $ab$. Fällt euch was auf? Wir haben keinen Zyklus. Die Sprache ist trotzdem regulär. Was machen wir hier mit unserem Pumping-Lemma? Nichts! Das Pumping-Lemma ist sinnvoll für unendliche Sprachen, endliche Sprachen sind der Definition nach bereits regulär. Das heißt aber nicht, dass das Pumping-Lemma hier nicht auch funktioniert.

Nicht vergessen: wir können mit dem Pumping-Lemma nicht zeigen, dass eine Sprache regulär ist (die Erfüllung des Pumping Lemma ist nicht hinreichend), wir können aber zeigen, dass sie das nicht ist, indem wir uns eine Pumping Lemma Zahl $j$ suchen, für Wörter, die größer sind als $j$ die Zerlegungen durchgehen und sie prüfen. Hat keine unserer unserer Zerlegungen die gewünschte Form, so ist die Sprache nicht regulär (kontextfrei). Warum größer als $j$?

Ganz einfach: für eine reguläre Sprache brauchen wir nur einen endlichen Automaten anzugeben, der für jedes Wort aus der Sprache einen akzeptierenden Zustand hat.

Setzen wir $j$ in unserem Beispiel z.B. auf $\geq 3$, bedeutet es, dass wir für alle anderen Worte $\leq 2$ bereits einen Automaten im Kopf haben, der für alle Wörter keiner als $3$ akzeptierende Zustände hat. Damit ist sind bzgl. der Worte die Sprache bereits als regulär entlarvt. Fehlt uns nur noch der Beweis der Regularität aller anderen Worte der Sprache.

Tja, wie viele Worte haben wir nun mit der Länge $\geq 3$? Keine! Wir haben also nichts mehr zu prüfen, da eine leere Menge ist der Definition nach regulär ist. Also ist die Sprache $L(G_2)$ nicht nur nicht nicht regulär (sorry für das komische Wortkonstrukt), sondern sogar durch die Angabe eines endlichen Automaten regulär. Das ist der Grund für die Regularität von endlichen Sprachen.

Merksatz: Endliche Sprachen sind immer regulär. Wir basteln uns hierzu einfach einen Automaten, der für jedes Wort, dass wir haben (denn die Menge unserer Worte ist endlich) einen akzeptierenden Zustand hat. Auch wenn die Länge der Worte $2^100$ ist, und der Automat Milliarden an akzeptierenden Zuständen hat. Hauptsache sie sind endlich. That's it.

In der Regel kennen wir das $j$ jedoch nicht, so dass wir nur eine Sprachdefinition, wie z.B. $L=\{(ab)^*\}$ haben und prüfen müssen ob die Sprache regulär ist. Bei Gelegenheit bringe ich hier ein paar explizite Beispiele. Bis dahin begnüge ich mich mit der Antwort zum Lernziel.

Antwort zum Lernziel: Mit dem Pumping Lemma lässt sich nachweisen, dass eine Sprache nicht regulär ist. Der Umkehrschluss gilt nicht, es gibt Sprachen, die nicht regulär sind aber das Pumping Lemma erfüllen. Dazu wird eine Pumping Lemma Zahl $j$ gesucht und für alle Worte, die länger sind als $j$ eine Zerlegung $uvw$ angegeben, so dass man das Midfix $v$ beliebig oft wiederholen kann und sich das Wort immer noch in der Sprache befindet. Tut es das nicht, so ist die Sprache nicht regulär. Wir weisen mit der Angabe von $v$ also quasi einen Zyklus im Automaten nach, mit dem man unendliche Worte durch Wiederholung von $v$ erstellen kann ohne die Sprache zu verlassen. Für endliche Sprachen gilt er Merksatz von oben.

Weiter geht es dann mit den letzten beiden Lernzielen im nächsten Beitrag. Fehler, Ergänzungen, Bermerkungen wie immer bitte ASAP in die Kommentare.

Vorletzte Kurseinheit. Und dazu noch ein eig. sehr schönes Thema. Die letzte KE und diese hier gehören ganz eng zusammen; ich kämpfe noch mit mir nicht einen einzigen Eintrag aus beiden Kurseinheiten zu gießen. Ich empfehle euch beide in einem Tab/Fenster aufzumachen damit Ihr beide Einträge vor der Nase habt und zwischen ihnen blättern könnt wenn in diesem Eintrag auf Sätze aus KE5 Bezug genommen wird.

Leider sind die letzten Kurseinheiten etwas dicker Kämpfen wir uns also wieder direkt durch die Lernziele.

Lernziel 1

Wie definiert man die von einem endlichen Automaten erkannte Sprache?

In dieser Kurseinheit sind Turingmaschinen mit einem Einweg-Ausgabeband ohne Arbeitsbänder im Fokus. Auch wenn man sie als Turingmaschinen notieren kann, wird eine andere Notation verwendet. Die der endlichen Automaten. Starten wir mit der Definition und einem Beispiel:

Endlicher (nichtdeterministischer) Automat

Quintupel $A=(\Sigma,Q,q_0,F,\delta)$ mit

$\Sigma$ als Eingabealphabet

$Q$ als endliche Menge der Zustände

$q_0\in Q$ als Anfangszustand

$F\subseteq Q$ als Menge der Endzustände

$\delta\subseteq Q\times\Sigma\times Q$ als Überführungsrelation

Dieser Teil der Definition macht euch sicher kaum Probleme, haben wir doch bereits Turingmaschinen in ähnlicher Weise definiert. Die Überführungsrelation führt einfach nur von einem Zustand aus $Q$ zu einem anderen Zustand aus $Q$ bei der Eingabe von einem Element aus dem Eingabealphabet $\Sigma$.

Nun definieren wir noch $\delta$:

$\delta^0=\{(q,\epsilon,q)\mid q\in{Q}\}$

$\delta^{n+1}=\{(p,xa,q)\mid x\in{\Sigma}^{*},a\in{\Sigma},\exists r\in{Q}.(p,x,r)\in\delta^{n}\wedge(r,a,q)\in\delta\}$

$\delta^{*} = \bigcup_{n\geq 0}\delta^n$ ist die transitive Hülle von $\delta$

Oha. Die induktive Definition der Überführungsrelation ist nicht so einfach. Aber warten wir das folgende Beispiel gleich ab, dann wird es klarer. In der transitiven Hülle sind auch indirekte Relationen drin, d.h. erreichen wir z.B. den Zustand $q_2$ bei der Eingabe von $a$ nur über $q_1$ ausgehend vom Startzustand $q_0$, so hätten wir eig. nur die Relationen $(q_0,a,q_1)$ und $(q_1,a,q_2)$. In der transitiven Hülle $\delta^{*}$ haben wir jedoch auch noch das indirekte Tripel $(q_0,a,q_2)$ drin.

Diese Tripel in $\delta^{*}$ können nicht nur einzelne Zeichen aus $\Sigma$ beinhalten, sondern können der Definition nach auch Worte sein. Führt uns z.B. die Eingabe $aaabbb$ zu einem Endzustand, so ist in der transitiven Hülle $\delta^{*}$ auch $(q_0,aaabbb,q)$ drin (wobei $q_0$ ein Anfangs- und $q$ ein Endzustand ist). Wird gleich im folgenden beispiel etwas verständlicher, versprochen.

Kommen wir nun zur akzeptierten Sprache $L(A)$:

$L(A):=\{x\in\Sigma^{*}\mid\exists q\in F.(q_0,x,q)\in\delta^{*}\}$

$L(A):=\{x\in\Sigma^{*}\mid\delta^{*}\cap(\{q_0\}\times\{x\}\times F)\neq\emptyset\}$

Es gilt also $x\in L(A)$ genau dann wenn $x$ den Anfangszustand in einen Endzustand überführt. Damit ist genau das die von dem endlichen Automaten $A$ erkannte Sprache $L(A)$. Nun kümmern wir uns um die Worte determiniert und vollständig.

determiniert, gdw. $\#\{q\in Q\mid(p,a,q)\in\delta\}\leq 1$ für alle $p\in Q,a\in\Sigma$

vollständig, gdw. $\#\{q\in Q\mid(p,a,q)\in\delta\}\geq 1$ für alle $p\in Q,a\in\Sigma$

Gar nicht so schwer: determiniert bedeutet, dass wir ausgehend vom Startzustand $q_0$ das Wort $x$ von links nach rechts ableiten und immer einen Folgezustand haben. Wenn es mal keinen Folgezustand gibt, so ist der Automat nicht vollständig und es gilt $x\notin L(A)$. Gibt es einen Zustand $p_n$ für die Eingabe $x$, wobei $n=lg(x)$ (Länge von $x$), so gilt: $x\in L(A)\Leftrightarrow p_n\in F$. D.h. soviel wie wenn die Länge von $x$ $n$ ist, so muss nach $n$ Schritten der Endzustand $p_n$ erreicht worden sein. Damit ist dann auch $x\in L(A)$. Landet man nach $n$ Berechnungsschritten nicht im Endzustand, so ist $x\notin L(A)$.

Nichtdeterminierte Automaten sind - genauso wie $NTM$ - reine Gedankenmodelle. Hierzu gibt es ein Beispiel im Skript, dass ich auch gerne anführen würde:

Beispiel: $A=(\Sigma,Q,q_0,F,\delta)$ mit

$\Sigma=\{a,b\}$ (Eingabealphabet)

$Q=\{0,1,2\}$ (Zustände)

$q_0=0$ (Startzustand)

$F=\{2\}$ (Endzustand)

$\delta=\{(0,a,0),(0,b,0),(0,a,1),(1,b,2),(2,a,2),(2,b,2)\}$

Wir zeichnen die Zustände als Kreise, weisen Start- und Endzustand entsprechend aus und jeder Übergang von einem Zustand zum anderen wird eine gerichtete und gekennzeichnete Kante zwischen diesen. Gibt es bereits einen Übergang, so müssen wir die Kante mit dem zusätzlichen Zeichen nur noch kennzeichnen.

Dieser ist nicht determiniert. Warum? Weil es für für eine Eingabe und einen Zustand zwei Folgezustände gibt: $(0,a,1)$ und $(0,a,0)$.

Auch ist er nicht vollständig: Warum? Weil wir im Zustand $1$ für die Eingabe $a$ keinen Folgezustand haben.

Wie sieht unsere transitive Hülle $\delta^{*}$ aus? Sie hat z.B. auch noch zusätzlich das indirekten Tripel $(0,b,2)$ drin. Und was ist mit dem $\delta^n$? Dazu kommen wir auch gleich. Ersteinmal stellen wir uns die Frage: Welche Sprache entscheidet der Automat?

Zunächst einmal können wir eine absolut beliebige Kombination aus $a$ und $b$ haben und verweilen im Zustand $0$: ${\{a,b\}}^{*}$. Erst wenn wir zum Zustand $2$ wollen, benötigen wir als Abschluss des ersten Teils der Zeichenkette ein $\{ab\}$. Und dort angekommen sind wir entweder fertig oder können im Zustand $2$ so verweilen, wie wir auch in Zustand $0$ verweilt haben: mit einer beliebigen Kombination aus $1$ und $b$: ${\{a,b\}}^{*}$.

Damit ist die von $A$ erkannte Sprache $L$, d.h. $L(A)={\{a,b\}}^{*}\{ab\}{\{a,b\}}^{*}$

Und nun kümmern wir uns um $\delta^n$ am versprochenen Beispiel (ebenfalls aus dem Skript geklaut).

Beispiel $a^4b^2\in L(A)$?

Wir müssen also schauen ob die Eingabe $x=aaaabb$ uns zu einem Endzustand (ein Zustand aus $F$) bringt oder nicht. In jedem Schritt bringt uns ein Zeichen aus dem Wort zu einem Folgezustand. Und wenn es mal keinen gibt oder wir nach $lg(x)=6$ Schritten noch keinen Endzustand erreicht haben, so ist das Wort nicht Teil unserer Sprache $L(A)$. Versuchen wir es also:

 $(0,\epsilon,0)\in\delta^0$

 $(0,a,0)\in\delta^1$ da $(0,a,0)\in\delta$

$(0,aa,0)\in\delta^2$ da $(0,a,0)\in\delta$

$(0,aaaa,0)\in\delta^3$ da $(0,a,0)\in\delta$

$(0,aaaaa,1)\in\delta^4$ da $(0,a,1)\in\delta$

$(0,aaaab,2)\in\delta^5$ da $(1,b,2)\in\delta$

$(0,aaaabb,2)\in\delta^6$ da $(2,b,2)\in\delta$

Wir sehen also, dass wir Ausgehend vom Startzustand $0$ zum Zustand $2$ gelangen, welcher ein Endzustand ist. Es liegt daher $(0,aaaabb,2)\in\delta^{*}$, woraus folgt, dass $a^4b^2\in L(A)$! Um zu zeigen, dass ein Wort zur Sprache gehört, müssen wir also einfach nur eine Zustandsfolge angeben, die die zu prüfende Eingabe in den Endzustand überführt. Braucht Ihr noch ein Beispiel um zu zeigen, dass eine Zeichenfolge nicht in $L(A)$ ist? Gerne.

Beispiel: $a^4\in L(A)$?

Spielen wir den Graphen mit der Eingabe $aaaa$ durch, so sehen wir, dass wir nie in im Endzustand $2$ landen. Wir bleiben immer nur in $0$ oder $1$. Damit ist $a^4\notin L(A)$? Probiert die nächsten beiden mal selbst.

Übung: $a^2 b^2\in L(A)$ $(aabb)$?

Lösung zeigen

Übung: $(ba)^3\in L(A)$ $(bababa)$?

Lösung zeigen

Übung: $(ba)\in L(A)$ $(ba)$?

Lösung zeigen

Antwort zum Lernziel: Damit ist die von einem endlichen Automaten $A$ erkannte Sprache $L$ die Menge der Worte über dem Alphabet $\Sigma$, die ausgehend von einem Startzustand $q_0$ den Automaten in einen Endzustand $q$ überführt und dabei nicht mehr Berechnungsschritte braucht als die Eingabe lang ist.

Lernziel 2

Wie kann man zu einem nichtdeterminierten endlichen Automaten einen determinierten konstruieren, der dieselbe Sprache erkennt?

Im Beitrag zu KE5 haben wir es bereits angedeutet: die Regeln aus den Grammatiken sind nichts weiter als Überführungsrelationen in Maschinen von einem Zustand zum anderen. Aus diesem Grund können wir rechtslineare Normalformgrammatiken in Automaten überführen. Dazu brauchen wir folgendes:

Transformation $T$ mit $T((\Pi,\Sigma,R,S)):=(\Sigma,\Pi,S,F,\delta)$ mit

$F=\{A\in\Pi\mid (A\rightarrow\epsilon)\in R\}$ und

$\delta=\{(A,a,B)\in\Pi\times\Sigma\times\Pi\mid (A\rightarrow aB)\in R\}$

Wir transformieren damit eine rechtslineare Normalformgrammatik in einen Automaten, so dass $L(G)=L(T(G))$ gilt. Die Definition von $F$ (unseren Endzuständen im Automaten) besagt lediglich, dass in die Menge der Endzustände unseres Automaten das Nonterminal reingehört. was auch als Regel für ein Nonterminal in den Regeln der Grammatik vorhanden ist und auf $\epsilon$ zeigt.

Mit $\delta$ ist es ähnlich. In die Überführungsrelationen gehören alle Regeln rein, die auf ein Terminal (unsere Eingabe im Automaten) und ein Nonterminal (unser Zustand im Automaten) zeigen. Das ist dann unser Zustandsübergang. Am besten ein Beispiel, oder? Nehmen wir dazu doch einfach die Grammatik, die wir im vorherigen Beitrag verwendet haben.

Beispiel: $G_1=(\Pi,\Sigma,R,S)$ mit $\Pi=\{S,B,C\}$, $\Sigma=\{a,b\}$, Startsymbol $S$ und den Regeln $R$:

$S\rightarrow aB$

$B\rightarrow bC$

$C\rightarrow\epsilon\mid aB$

Wir müssen also aus der rechtslinearen Normalformgrammatik $G_1$ einen endlichen Automaten basteln. Weder am Alphabet $\Sigma$, noch an den Zuständen (Nonterminalen) $\Pi$ oder am Startzustand $S$ haben wir was zu kamellen. Wir brauchen die Menge der Endzustände $F$ und unsere Überführungsrelationen $\delta$.

Fangen wir mit dem Endzustand $F$ an. Schaut noch einmal die Definition von $F$ oben an. Wir suchen also in den Regeln $R$ unserer Grammatik $G_1$ nach der Regel von der Form $(A\rightarrow\epsilon)$. Die einzige Regel, die so aussieht ist die Regel für $C\rightarrow\epsilon\mid aB$. Damit haben wir den Endzustand der Grammatik $C$ nun in unserer Automaten-Menge $F$. Hätten wir mehr Regeln, die auf ein $\epsilon$ zeigen, so hätten wir auch mehr Endzustände.

Jetzt die Überführungsrelationen $\delta$: wir transformieren alle Regeln der Grammatik mit der Form $(A\rightarrow aB)$ in die Überführungsrelation für dem Automaten mit der Form $(A,a,B)$:

$S\rightarrow aB\Rightarrow(S,a,B)$

$B\rightarrow bC\Rightarrow(B,b,C)$

$C\rightarrow aB\Rightarrow(C,a,B)$

That's it. Wie sieht der Automat nun aus? So:

Fertig! Wir sehen auch hier, dass er nicht vollständig ist: es fehlt im Zustand $S$ der Folgezustand für die Eingabe eines $b$. Aber er ist determiniert, da wir nicht mehrere Folgezustände für eine Eingabe haben.

Nachdem das nun geklärt ist, kümmern wir uns um die Überführung von nichtdeterminierten Automaten in determinierte. Der Vorteil von letzteren liegt darin, dass diese sich mittels Boole'schen Schaltwerken realisieren lassen. Wäre doch schön wenn wir dazu die nichtdeterminierten Automaten in determinierte überführen könnten...

Beispiel: der Automat aus dem ersten Beispiel mit $A=(\Sigma,Q,q_0,F,\delta)$ mit

$\Sigma=\{a,b\}$ (Eingabealphabet)

$Q=\{0,1,2\}$ (Zustände)

$q_0=0$ (Startzustand)

$F=\{2\}$ (Endzustand)

$\delta=\{(0,a,0),(0,b,0),(0,a,1),(1,b,2),(2,a,2),(2,b,2)\}$

und dem zugehörogen Graphen

Die Menge der neuen Zustände ist maximal $2^Q = 2^3 = 8$. Wobei wir nicht alle benötigen werden. Dazu stellen wir eine Tabelle auf, die uns am Ende zeigt welche Übergänge und welche Zustände wir haben. Wir fangen einfach mal an, die Inhalte der Spalten erschließen sich dann direkt:

In der ersten Zeile, in Spalte $P$ steht der Startzustand. In Spalte $a$ und $b$ stehen die jeweils erreichbaren Zustände bei der jeweiligen Eingabe, ausgehend vom Zustand in Spalte $P$. D.h. ausgehend von Startzustand $0$ erreichen wir bei der Eingabe von $a$ Folgezustand $0$ und $1$ und bei der Eingabe von $b$ nur Zustand $0$. In der Spalte $W\setminus{V}$ befindet sich die Elemente der Menge $W=\{\{0,1\},\{0\}\}$ ohne die Elemente der Menge $V=\{\{0\}\}$, also nur $W\setminus{V}=\{\{0,1\}\}$. Damit haben wir die erste Zeile aufgebaut.

Für die Spalte $P$ in der zweite Zeile nehmen wir ein Element aus der Menge $W\setminus{V}=\{\{0,1\}\}$. Viel Auswahl haben wir hier nicht (hätten wir eine, so wäre die Auswahl willkürlich, sie würde nur die Reihenfolge der Zeilen beeinflussen). Nun werden wieder die erreichbaren Folgezustände, ausgehend von Startzustand $0$ und $1$ bei der Eingabe von $a$ und $b$ in den folgenden Spalten notiert und in der letzten Spalte wieder $W\setminus{V}$ eingetragen. Das machen wir solange, bis die Menge $W\setminus{V}$ leer ($W\setminus{V}=\emptyset$) ist. Am Ende haben wir die folgende Tabelle:

Aus dieser können wir nun alle notwendigen Zustände (Spalte $P$) und die Folgezustände (Spalten $a$ und $b$) ableiten. Alle Zustände aus Spalte $P$, die die Zahl eines Endzustandes ($2$) des ursprünglichen Automaten beinhalten, werden ebenfalls zu Endzuständen. Am Ende kommt daher folgender Graph raus:

Wenn wir die Wertetabelle dazu aufstellen sehen wir auch, dass wir einen Zustand wegkürzen können (wie in Computersysteme 1 und 2).

Zustand $02$ und $012$ sind äquivalent und damit kürzbar (wenn man zur $b$-Kante von $02$ noch $a$ hinzufügt).

Antwort zum Lernziel: zu einem nichtdeterminierten Automaten kann man einen determinierten Automaten konstruieren, der dieselbe Sprache erkennt, indem man eine neue Zustandsmenge definiert, die maximal aus der Potenzmenge $2^Q$ der ursprünglichen Zustände $Q$ führt. Die Menge der benötigten Zustände ergibt sich aus allen erreichbaren Zuständen.

Diese neuen Automaten werden Potenzautomaten genannt. Damit lässt sich festhalten, dass man zu jedem endlichen, nicht-deterministischen Automaten einen deterministischen Automaten angeben kann, der die selbe Sprache erkennt.

Da die Namen der neuen Zustände aus den Namen der Ursprungszustände bestehen, können die gerichteten Kanten auch zu den neuen Zuständen problemlos gezogen und so die Zustandsübergänge im neuen Graphen modelliert werden. Durch die Benennung lassen sich auch die Endzustände im neuen, deterministischen Graphen identifizieren: jeder neue Zustand, der in seinem neuen Namen den Namen eines ursprünglichen Endzustands beinhaltet, wird ebenfalls ein Endzustand.

Das war der erste Teil von KE6. Wer Fehler findet: ab in die Kommentare.

Update 2: Markus hat eine Ungenauigkeit im Lernziel 8 gefunden. Ist korrigiert, Danke.

Update: Beispiel für die regulären Ausdrücke, sowie Gleichungen für die Funktion $L$ aus Lernziel 5 hinzugefügt. Ebenfalls Antworten zu allen Lernzielen verfasst.

Noch drei Kurseinheiten, dann ist TIB auch schon vorbei. In dieser Kurseinheit geht es um Grammatiken. Häufig wird in der Literatur zunächst die Grammatik eingeführt und anschließend die Komplexität, aber das soll uns hier nicht weiter stören. Also wieder entlang der Lernziele.

Lernziel 1

Was ist eine Grammatik $G$, wie definiert man die Sprache $L(G)$?

Eine Grammatik ist ein Modell zur Definition konkreter Sprachen. Die erste Definition im Skript ist die der formalen Sprache (letzter Punkt ist der aus dem Skript, alle anderen sind geklaut aus dem Buch von Dirk. W. Hoffmann).

Automat: Maschine zum Erkennen von Sprachen.

Alphabet $\Sigma$, endliche Menge von Symbolen.

Jedes Element $a$ ist ein Zeichen des Alphabets.

Jedes Element $\omega$ ist ein Wort über $\Sigma$.

Jede Teilmenge $L\subseteq\Sigma^{*}$ ist eine formale Sprache über $\Sigma$.

$\Sigma^{*}$ nennt man auch Kleen'sche Hülle. Dort sind alle endlichen Symbolsequenzen drin, die wir mit den Symbolen aus $\Sigma$ basteln können. Auch ist dort das leere Wort $\epsilon$ enthalten (im $\Sigma^{+}$ jedoch nicht). Sagen wir z.B., dass $L$ über dem Alphabet $\Sigma=\{0,1,2,...,9\}$ die Menge der Ziffernfolgen ist, die einer Primzahl entsprechen, so wäre z.B. $2,3,5,7,...\in L$, während $1,4,6,8,...\notin L$ ist.

Uns geht es aber nicht um die Bedeutung der Worte, sondern um die syntaktischen Anteile.

Überabzählbarkeit

Ein wichtiger Aspekt ist, dass die Menge der formalen Sprachen über $\Sigma$ (also $L_{\Sigma}$) überabzählbar unendlich ist. Für eine Abzählbarkeit brauchen wir eine Bijektion zwischen den natürlichen Zahlen $\mathbb{N}$ und der abzuzählenden Menge. Da jedoch die menge aller Sprachen über einem Alphabet $L_{\Sigma}$ gleich der Mächtigkeit aller Teilmengen von $\Sigma^{*}$ ist, gilt $L_{\Sigma}=P(\Sigma^{*})$. Das $P$ steht für Potenzmenge. Und da Potenzmengen einer beliebigen Menge eine größere Mächtigkeit haben, als die menge selbst ist $L_{\Sigma}$ überabzählbar. Das Beweisverfahren vom zweiten Cantor'schen Diagonalargument findet hier Anwendung.

Kommen wir aber nun zu dem Kerl, der das ganze verbrochen hat: Noam Chomsky. Von ihm stammen auch ein paar spannende Bücher. Der Kerl lebt, wie Stephen A. Cook aus dem vorherigen Beitrag zu KE4, auch noch und lehr am MIT. Mit etwas Kleingeld für die Studiengebühren oder genügend Gehirnschmalz für das Doc-Program des MIT kommt Ihr also noch in den Genuss seiner Lehren.

Der Typ hat also ein einfaches, formales Modell einer Grammatik eingeführt, mit dem man Grundstrukturen einer Sprache beschreiben kann. Im Skript ist die Grammatik als Virertupel definiert, wie in den meisten anderen Büchern auch. Hier lässt es sich also sehr gut auch mit Zusatzliteratur arbeiten. Allgemein halte ich Teil B der theoretischen Informatik für "gelungener". Ob das nun daran liegt, dass es wirklich besser ist oder ich mich mittlerweile von TIA habe abstumpfen lassen, möchte ich an dieser Stelle nicht weiter analysieren.

Definieren wir also die Grammatik als Vierertupel $G=(\Pi,\Sigma,R,S)$:

$\Pi$ Nichtterminalalphabet, endliche Variablenmenge (Platzhalter, auch Nonterminalsymbole genannt. Lassen sich ersetzen)

$\Sigma$ Terminalalphabet, $\Pi\cap\Sigma=\emptyset$ (nicht weiter ersetzbare Sprachberstandteile, auch Terminale genannt).

$R$ Regelmenge/Produktion mit $R\subseteq((\Sigma\cup\Pi)^{*}\setminus{\Sigma^*})\times(\Sigma\cup\Pi)^{*}$ (nicht erschrecken, Erklärung kommt gleich)

$S\in\Pi$ Startsymbol (damit beginnt immer die Ableitung)

Das ist auch gleichzeitig die Definition der Typ-0-Grammatik. Wahrscheinlich hängt Ihr gerade an der Definition der Regelmenge, oder? Wir definieren hier eine Ableitungsrelation. Es gilt zudem $x\Rightarrow^{*}y$ gdw. das Wort $y$ aus dem Wort $x$ in endlich vielen Schritten anhand der Regeln aus $R$ abgeleitet werden kann.

Beispiel: $G=(\Pi,\Sigma,R,S)$ mit $\Pi=\{S,L,R\}$, $\Sigma=\{\#,a\}$ und Regeln $R$ (KE5, S. 9)

$S\rightarrow\#aL\#$

$aL\rightarrow La$

$\#L\rightarrow\#R$

$Ra\rightarrow aaR$

$R\#\rightarrow L\#$

$R\#\rightarrow\#$

Aus diesen Regeln können wir nun Zeichenfolgen ableiten, die zur Sprache $L$ mit der Grammatik $G$ gehören, d.h. Fragen beantworten, wie z.B. $\#aa\#\in L(G)$? Wir müssen nur aus $\#aL\#$ nach endlich vielen Schritten $\#aa\#$ anhand dieser Regeln erzeugen können. Ist das der Fall, so haben wir $\#aa\#\in L(G)$ bewiesen (und ja, es ist tatsächlich $\#aa\#\in L(G)$, probiert es mal selbst).

Übung: $\#aa\#\in L(G)$?

Lösung zeigen

Eine weitere, spannende Definition ist, dass die

von Typ-0-Grammatiken erzeugten Sprachen genau die rekursiv aufzählbaren (semi-entscheidbaren) Wortmengen sind.

Beweisidee: Hierzu wird für eine Bandmaschine eine Grammatik konstruiert, wobei die Regeln der Grammatik die Einzelschrittrelationen der Maschine sind. Die Sprache ist dann genau die Menge der von der Maschine erzeugten Worte. In umgekehrter Richtung wird eine $NTM$ erstellt, die vom Startsymbol ausgeht die Regeln als Einzelschrittrelationen anwendet und anhält wenn das Eingabewort abgeleitet wurde. Nehmen wir also an, dass unsere Maschine aus der Eingabe $aa$ in einem Schritt eine Ausgabe $aaaa$ erzeugt. Das entspräche dann eine Regel in unserer Grammatik: $aa\rightarrow{aaaa}$.

Achtung: Die Menge der rekursiv aufzählbaren (semi-entscheidbaren) Sprachen ist gegenüber

• Kleene'scher Hüllenbildung,
• Konkatenation,
• Schnitt und
• Vereinigung

abgeschlossen, nicht jedoch gegenüber dem Komplement (geklaut aus der Wikipedia). Da das aber nicht so deutlich im Skript raus kam, wollte ich das hier etwas hervorheben.

Antwort zum Lernziel: eine Grammatik $G$ ist ein Modell zur Definition konkreter Sprachen. Sie ist ein 4-Tupel mit Terminalen, Nonterminalen, dem Alphabet und dem, was eine Grammatik erst ausmacht: den Regeln. Mittels diesen Regeln, auch Produktionen genannt, wird eine Sprache $L(G)$ erzeugt, d.h. eine Sprache $L$ über der Grammatik $G$.

Lernziel 2 (Update)

Welche Sprachklasse wird durch Grammatiken definiert?

Hier schwimme ich gerade etwas, da ich nichts mit der Frage anzufangen weiß. Grammatiken definieren unterschiedliche Sprachklassen. Je nach gewählter Grammatik werden unterschiedliche Sprachklassen (entscheidbare oder semi-entscheidbare Sprachen) definiert. Wer die Frage anders interpretiert und eine andere Antwort hat, bitte in die Kommentare damit.

Wieder mal ein großer Dank an Barbara, mit der die Antwort zum Lernziel erarbeitet wurde.

Zunächst einmal noch zur Erinnerung: Die Sprachklassen sind unsere Sprachen, die durch Typ-X-Grammatiken definiert werden. Wir fangen ab Typ-0 an zu zählen, hierzu gehört jede Grammatik, d.h. die absolute Ober-Sprachklasse, die durch Grammatiken definiert wird ist die Typ-0-Sprachklasse. Erst durch Einschränkung unserer Grammatiken zu Typ-1-, -2-, und -3-Grammatiken werden weitere Sprachklassen, eben die Typ-1-, -2-, und -3-Sprachen, definiert, die aber alle eine echte Teilmenge der Typ-0-Sprachklasse sind (diese Inklusionsberziehung ist wichtig, daher merken!).

Nicht falsch verstehen: es gibt auch Sprachen, die nicht von Grammatiken erzeugt werden können (Überabzählbarkeit der Potenzmenge, aber dazu kommen wir später noch). Die Typ-0-Sprachen sind eine echte Teilmenge dieser. In den folgenden Beiträgen wird die Beziehung zwischen den einzelnen Sprachklassen noch deutlicher hervorgehoben, also noch etwas Geduld

Durch was ist die Oberklasse Typ-0, die von Grammatiken erzeugt werden kann, also definiert? Durch eine Turingmaschine, die hält wenn es ein Wort der Typ-0-Sprachklasse akzeptiert und nicht hält (oder sich in einem anderen Zustand befindet) wenn das Wort nicht aus der Typ-0-Sprachklasse ist. Das ist genau die Definition von semi entscheidbaren/rekursiv aufzählbaren Wortmengen: die Typ-0-Sprachen sind genau die von Turingmaschinen akzeptierten Sprachen.

Beweisidee

$TM\rightarrow Grammatik$

Das ist die eine Richtung. Zu einer Turingmaschine $M$ wird eine Grammatik $G$ erzeugt, deren Regeln im wesentlichen die Einzelschrittrelationen sind. Die von der Grammatik $G$ erzeugte Sprache $L(G)$ ist dann genau die Menge der Worte, die $M$ erzeugt.

Vorgehensweise: die Grammatik simuliert mit ihren Ableitungsregeln die Einzelschrittrelationen (Konfigurationsübergänge) der TM. Dabei werden alle möglichen Eingabewörter, Anfangskonfigurationen und die Konfigurationsübergänge als Regeln konstruiert (Nonterminal als Zustand und Folgezustand, Terminal als Eingabezeichen). Dabei wird die Akzeptanz eines Wortes durch das Löschen von Nonterminalen ($C\rightarrow\epsilon$) simuliert und der Ableitungsvorgang so gestoppt.

Damit erzeugt die Grammatik $G$ genau die Worte, die von der TM $M$ akzeptiert werden.

$Grammatik\rightarrow TM$

Für die umgekehrte Richtung wird eine NTM $T$ zu einer Typ-0-Grammatik $G$ erzeugt, welche vom Startsymbol der Grammatik ausgehend die Regeln der Grammatik anwendet und anhält wenn das Wort abgeleitet wurde. Anschließend wir die NTM durch eine TM simuliert.

Vorgehensweise: Die TM simuliert die Ableitungsregeln. Dabei werden ableitbare Worte von der TM schrittweise auf das Hilfsband (man könnte auch ohne Hilfsband arbeiten) geschrieben und mit der Eingabe verglichen. Die Maschine akzeptiert das Wort, bzw. terminiert im Endzustand genau dann wenn $\omega\in L(G)$.

Damit akzeptiert die TM genau die Worte, die von der Grammatik erzeugt werden.

Beispiel: kontextsensitive Grammatik $G_0=(\Pi,\Sigma,R,S)$ mit $\Pi=\{S,B,C\}$, $\Sigma=\{a,b\}$ und Regeln $R$

$S\rightarrow aSBC\mid aBC$

$aB\rightarrow ab$

$bB\rightarrow bb$

$bC\rightarrow bc$

$cC\rightarrow cc$

$CB\rightarrow BC$

Diese Grammatik $G_0$ erzeugt die fiese, kontextsensitive Typ-0-Sprache $L_0=\{a^n b^n c^n\mid n\in\mathbb{N}\}\Rightarrow(abc,aabbcc,...)$. Nun müssen wir zu der Grammatik eine Turingmaschine angeben, die  ein Wort aus dieser Sprache durch erreichen des Endzustands akzeptiert und ansonsten in einem anderen Zustand hält oder nicht terminiert.

Exkurs:

Es stellt sich die Frage, warum müssen wir eine Turingmaschine angeben? Warum geht nichts anderes? Leider haben wir noch nicht die einzelnen Sprachklassen charakterisiert, evtl. wäre es dann bereits jetzt klar. Die Turingmaschine ist das mächtigste Werkzeug das wir haben, sie ist genauso mächtig wie Registermaschinen. Nur, dass Registermaschinen auf Zahlen operieren und Turingmaschinen auf Worten.

Und selbst mit den Turingmaschinen können wir nicht alle Sprachen angeben, denn die Anzahl der Turingmaschinen ist, wie wir wissen, abzählbar unendlich (zweites Diagonalrgument von Cantor). Die Menge aller Sprachen über $\Sigma^{*}$ ist es jedoch nicht (Potenzmenge, siehe oben). Damit können wir, wie erwähnt, nicht alle Sprachen mit Turingmaschinen akzeptieren. Wenn wir die Turingmaschine einschränken, können wir eine immer kleinere Menge innerhalb dieser Obersprachklasse (Typ-0) abdecken, bis wir irgendwann bei den regulären Sprachen (Typ-3) angelangt sind, die von einem endlichen Automaten akzeptiert wird, was im Prinzip nichts weiter ist, als eine maximal eingeschränkte TM.

Aber weiter im Text: Was wir nun tun müssen, ist es die Ableitungssequenz umzukehren. Denn unsere TM nimmt ein Wort entgegen anstatt es zu produzieren. Dazu muss es das Wort in das Startsymbol zurückführen. Wenn es der TM gelungen ist, gilt das Wort als akzeptiert. Können mehrere Regeln angewandt werden, so müssen wir unsere TM als NTM konstruieren.

Wir haben uns zwar darauf beschränkt Einband-TM zu betrachten, aber für die Grammatik $G_0$ war ich etwas faul und habe auf ein Arbeitsband zurückgegriffen. Mit etwas mehr Zuständen schaffen wir das ganze Spiel auch auf einer Einband-TM. In der folgenden Grafik wird die TM aufgezeigt, die unsere Sprache akzeptiert (ich habe mein neues Spielzeug benutzt, kann ich nur empfehlen). Das JFLOP-File könnt Ihr hier downloaden.

Erklärung der Grafik: $a;a,R\mid B;A.R$ bedeutet z.B. Lese auf dem Eingabeband ein $a$ und gehe auf diesem nach rechts. Lese gleichzeitig auf dem Hilfsband ein $B$ (Blank), schreibe ein $A$ und gehe auf dem Hilfsband nach rechts.

Funktionsweise: wir laufen das Wort ab und schreiben so viele $A's$ auf das Hilfsband, wie wir $a's$ auf dem Eingabeband haben. Anschließend gehen wir die $b's$ durch und ersetzen die gleiche Anzahl an $A's$ auf dem Hilfsband, wie $b's$ auf dem Eingabeband vorhanden sind durch $C's$. Nun werden die $c's$ auf dem Eingabeband eingelesen und die gleiche Anzahl der $C's$ auf dem Hilfsband gelöscht.

Jetzt wandern wir auf beiden Bändern so weit zurück, wie unser Eingabewort lang ist. Finden wir dann nur noch Blanks auf dem Hilfsband und sind wir am Anfang unseres Eingabewortes angelangt, wird das Wort akzeptiert.

Ladet euch die Datei für das JFLOP herunter und probiert es selbst aus (Links zu JFLOP und der Datei oberhalb der Grafik).

Antwort zum Lernziel: die Typ-0-Grammatiken definieren die Typ-0-Sprachklasse. Diese Sprachen sind genau die von Turingmaschinen akzeptierten/semi entscheidbaren/rekursiv aufzählbaren Wortmengen.

Sie bilden die Oberklasse aller Sprachen, jedoch kann es auch Sprachen geben, die nicht von Grammatiken erzeugt werden können. Dies wird mit dem gleichen Verfahren bewiesen, wie es auch im zweiten Diagonalargument von Cantor angewandt wurde: es gibt einfach mehr Sprachen (Produktmenge über $\Sigma$), als es Turingmaschinen geben kann (Stichwort: Überabzählbarkeit).

Lernziel 3

Was sind Typ-1-, Typ-2-, Typ-3-Grammatiken?

Neben den Typ-0-Grammatiken gibt es auch noch weitere. Das ist dann die Chomsky-Hierarchie. Der werte Herr - Sprachwissenschaftler - hat 1957 ein Regelwerk erstellt um die Grammatiken in vier Klassen einzuteilen. Diese sind wie folgt:

• Typ-0-Grammatiken: Phrasenstrukturgrammatiken
  Die haben wir eben kennengelernt. Jede Grammatik ist auch immer eine Typ-0-Grammatik. Es gibt keine weiteren Einschränkungen als die erste Definition zum Vierertupel $G=(\Pi,\Sigma,R,S)$ in diesem Beitrag.
  Automat: Zu jeder Typ-0-Sprache existiert eine TM, die diese Sprache akzeptiert (eine TM ist unser stärkstes Berechnungsinstrument). Da wir eine NTM durch eine TM simulieren können (die TM simuliert einfach alle Berechnungspfade der NTM, können wir hier uns auf eine TM beschränken).

• Typ-1-Grammatiken: Kontextsensitive Grammatiken (kontextsensitive Sprache)
  Für die Produktionsbeziehungen $l\rightarrow r$ gilt die Beziehung $\mid r\mid\geq\mid l\mid$. D.h. die Anwendung der Produktion führt nie zu einer Verkürzung der Zeichenkette. Ganz einfach, oder?
  Beispiel: $aA\rightarrow aBb$
  Automat: Zu jeder Typ-1-Sprache existiert eine linearbeschränkte TM, die diese Sprache akzeptiert. Die lineare Beschränkung ist der Tatsache geschuldet, dass wir die Grammatik eingeschränkt haben. Die rechte Seite der Produktion wird nie kleiner. Weil wir in der TM die Berechnung umkehren (wir leiten in der Maschine ein gegebenes ein Wort zu seinem Ursprung, statt wie in der Grammatik den Ursprung zum Wort), können wir nie mehr Zeichen auf dem Band bekommen als die Eingabe initial lang war.

• Typ-2-Grammatiken: Kontextfreie Grammatiken (kontextfreie Sprache)
  Die linke Seite der Produktionsregeln besteht immer nur aus einer einzigen Variable, es gilt also: $l\rightarrow r\Rightarrow l\in\Pi$. Auch nicht viel schwerer als Typ-1.
  Beispiel: $A\rightarrow aBb$.
  Automat: Zu jeder Typ-2-Sprache existiert ein nichtdeterministischer Kellerautomat, der diese akzeptiert. Der Kellerautomat ist weniger mächtig als die TM (zumindest mit nur einem Speicher), wir können uns also auf ein weniger mächtiges Konstrukt stützen. Warum? Weil das wieder der noch mehr eingeschränkten Grammatik geschuldet ist. Aber normale Automaten reichen nicht aus, da hier beliebig viele Nonterminale auftreten können. Wir brauchen also noch einen Speicher. Da wir uns auf Linksableitungen beschränken (das am links stehende Nonterminal wird ersetzt) können und somit immer nur auf das erste Zeichen im Kellerspeicher zugreifen, können wir diese Linksableitungen einer kontextfreien Grammatik mit unserem Kellerautomaten (NTM mit einem Einweig-Eigabeband und einem Kellerspeicher) simulieren.

• Typ-3-Grammatiken: Reguläre Grammatiken (rechtslineare Sprache)
  Sie sind zunächst kontextfrei und die rechte Seite der Produktion besteht entweder aus einem leeren Wort $\epsilon$ oder einem Terminalsymbol, dem ein Nichtterminalsymbol folgt. Formal: $l\rightarrow r$ mit $l\in\Pi$ und $r\in\{\epsilon\}\cup\Sigma\cdot\Pi$ (Danke Gerald, vorher stand da $r\in\{\epsilon\}\cup\Sigma\cup\Pi$, blödes CopyPaste). Das war jetzt etwas schwieriger. Wenn man die Definition langsam liest, erschließt sich einem der Satz etwas besser.
  Beispiel: $A\rightarrow aB$
  Automat: Zu jeder Typ-3-Sprache existiert ein endlicher Automat, der diese akzeptiert. Noch eine weitere Einschränkung. Hier brauchen wir nicht einmal einen Speicher, sondern kommen mit Zuständen aus.

Nochmal zur Erinnerung: ein Terminalsymbol ist ein Symbol, dass nicht weiter ersetzt werden kann. Ein Nichtterminalsymbol jedoch ist ein Platzhalter, den man durchaus ersetzen kann.

Zwischen den Sprachen gilt die folgende echte Inklusionsbeziehung: $L(Typ-0)\supset L(Typ-1)\supset L(Typ-2)\supset L(Typ-3)$. Grafisch dargestellt sieht der ganze Spaß so aus:

Im Skript wird ebenfalls eine Verbindung zwischen den Komplexitätsklassen und den Sprachen in der Chomsky-Hierarchie konstruiert, so dass folgende Aussagen äquivalent sind:

$L$ ist eine Typ-1-Sprache (kontextsensitiv).

$L\in NBAND(n)$

Das liegt an folgenden Dingen: keine Regel kann das Wort verkürzen, außer $S\rightarrow\epsilon$. Damit haben wir $lg(x)\leq lg(y)$ (wir leiten von $x$ auf $y$ ab) wenn wir nicht auf ein leeres Wort ableiten. Haben wir zudem z.B. eine Eingabe $x$ von der wir prüfen wollen ob sie zu der Sprache $L(G)$ gehört oder nicht, leiten wir ausgehend vom Startsymbol ab. Da die Länge des abgeleiteten Wortes aufgrund der Einschränkung für Typ-1-Sprachen sich nie verkürzen kann, können wir die Berechnung verwerfen wenn wir ein Wort ableiten, dass länger als unsere Eingabe ist.

Noch eine Kleinigkeit: wegen dem Satz von Savitch ist auch jede kontextsensitive Sprache in Exponentialzeit und $BAND(n^2)$ entscheidbar.

Antwort zum Lernziel: die Grammatiken werden, ausgehend von Typ-0, immer restriktiveren Einschränkungen für die Produktionsregeln unterworfen. Dadurch wird es möglich die Obermenge der Typ-0-Sprachen (semi-Entscheidbarkeit) immer weiter einzuschränken, bis man letztlich zu den Typ-3-Sprachen (reguläre Sprachen, vollständig entscheidbar durch einen endlichen Automaten) kommt. Es ergibt sich so eine echte Inklusionsbeziehung zwischen den Sprachklassen und eine Hierarchiebeziehung, auch Chomsky Hierarchie genannt.

Diese Sprachen spielen eine große Rolle bei den Programmiersprachen: Typ-2-Sprachen (kontextfrei) erlauben z.B. eine Interpretation von Ausdrücken dieser Sprache, so dass entschieden werden kann ob ein Ausdruck den Regeln der Grammatik entspricht (Parser) oder nicht.

Lernziel 4

Wie definiert man reguläre Mengen?

Im Skript steht, dass jeder Informatiker die regulären Sprachen und ihre Eigenschaften kennen muss. Dem wollen wir uns also nicht verschließen. Die Menge der regulären Sprachen ist die kleinste Sprachklasse in der Chomsky-Hierarchie. Sie sind rechtslinear (der Syntaxbaum neigt sich nach unten rechts weg) und werden von determinierten und nichtdeterminierten Automaten erkannt. Automaten werden leider in der nächsten Kurseinheit besprochen, was ich schade finde. Das würde zum Verständnis dieser KE sicherlich beitragen. Aber sei es drum: wenn euch etwas noch nicht zu 100% klar ist, schaut in die nächste KE.

Aber weiter im Text: Die herausgehobene Position der regulären Sprachen in der Informatik basiert auf deren Verwendung, z.B. als reguläre Ausdrücke in Suchmustern. Bevor wir darauf näher eingehen, definieren wir zunächst die Operationen auf den Sprachen über einem festen Alphabet, die auf Wortmengen zugeschnitten sind:

$X\cdot Y := \{xy\mid x\in X, y\in Y\}$. Komplexprodukt von $X$ und $Y$.

$X^n(n\geq0)$ als $X^0=\{\epsilon\}$ und $X^{n+1}=X^n\cdot X$

$X^{*}=\bigcup_{n\geq 0} X^n$. Sternoperation.

$X^{+}=\bigcup_{n\geq 0} X^n$ ($X^*\cdot X$)

$\overline{X}=\Sigma^{*}\setminus X$ (Komplement bzgl. $\Sigma^{*}$)

$X^{R}=\{x^R\mid x\in X\}$ (Spiegelung)

Definieren wir mal die reguläre Menge/reguläre Sprache wie im Skript:

$\emptyset$ ist eine reguläre Menge über $\Sigma$. Wenn $a$ ein Element von $\Sigma$ ist, so ist die Wortmenge $\{a\}$ eine reguläre Menge über $\Sigma$.

Sind $X$ und $Y$ reguläre Mengen, so ist es auch $X\cup Y, X\cdot Y$ und $Y^{*}$. Die regulären Mengen sind also bzgl. der genannten Operationen abgeschlossen.

Eine Menge nennt man regulär wenn sie in endlich vielen Schritten mit den genannten Operationen in der letzten Definition erzeugt werden kann. Mit $REG_n$ werden im Skript die regulären Mengen über $\Sigma$ genannt, die man in $n$ Schritten erzeugen kann. Da wir bereits die rekursiv aufzählbaren (semi-entscheidbaren) Sprachen hatten, haben die regulären Sprachen einen weiteren Vorteil:

Jede reguläre Menge/Sprache ist rekursiv (entscheidbar)

Jede endliche Menge $M\subseteq\Sigma^{*}$ ist regulär

Achtung: Damit bilden sie eine echte Teilmenge in den Typ-0-Sprachen (die Menge der rekursiven (entscheidbaren) Sprachen ist eine Teilmenge der rekursiv aufzählbaren Sprachen). Die regulären Sprachen erweisen sich als abgeschlossen unter

• Komplementbildung,
• Konkatenation,
• Schnitt,
• Vereinigung und
• Bildung des Kleeneschen Abschlusses.

Bei Gelegenheit werde ich ein paar Beispiele zu den vorgestellten Operationen in diesen Beitrag einbauen.

Noch ein Nachtrag aus der Wikipedia zum Thema: Möchte man zeigen, dass eine Sprache regulär ist, so muss man sie auf eine reguläre Grammatik, einen endlichen Automaten (z. B. einen Moore-Automaten) oder einen regulären Ausdruck oder auf bereits bekannte reguläre Sprachen zurückführen. Für einen Nachweis, dass eine Sprache  nicht regulär ist, kann man das Pumping-Lemma verwenden (dazu stand leider in dieser KE nichts, aber im Buch von Hoffmann schon. Wenn auch in KE6 und 7 nichts dazu steht, schreibe ich das hier ausführlich hin).

Antwort zum Lernziel: am Anfang stehen die einzelnen Zeichen $a$ unseres Alphabets $\Sigma$. Diese nennen wir regulär. Alles, was wir aus diesen Zeichen mittels Vereinigung, Verkettung und Sternoperation (Kleen'sche Hülle) und der leeren Menge $\emptyset$ (welche der Definition nach ebenfalls regulär ist) basteln können ist ebenfalls regulär.

Haben wir reguläre Mengen $X$ und $Y$, so ist die Menge, die durch die genannten Operationen auf diesen Mengen entsteht... ja, genau: auch regulär.

Lernziel 5

Welche Sprache wird durch einen regulären Ausdruck definiert?

Kommen wir nun zu den regulären Ausdrücken. Mit ihnen können wir reguläre Sprachen beschreiben. Damit kann jede Erzeugungsvorschrift durch einen regulären Ausdruck verschlüsselt werden, so dass wir durch die Syntax (regulärer Ausdruck) die reguläre Sprache (Semantik) bekommen.

Damit ist $L$ unsere Semantikfunktion, die zu jedem regulären Ausdruck $\alpha$ eine Sprache aus $\Sigma^{*}$ zuordnet, sie fungieren als eine Art "Name" für die regulären Mengen (der Satz ist aus dem Skript. Ich finde ihn aber sehr anschaulich und habe ihn deswegen für den Beitrag geklaut).

Definieren wir sie wieder zunächst:

Sei $\Sigma$ ein beliebiges Alphabet, $Reg(\Sigma)$ die Menge der regulären Ausdrücke, die induktiv aus folgenden Regeln gebildet wird:

$\emptyset,\epsilon\in Reg(\Sigma)$

$\Sigma\subset Reg(\Sigma)$

Wenn $r\in{Reg(\Sigma)}$ und $s\in{Reg(\Sigma)}$, dann sind auch $rs$ und $(r\mid s)\in{Reg(\Sigma)}$

Wenn $r\in{Reg(\Sigma)}$, dann sind auch $(r)$ und $r^*\in{Reg(\Sigma)}$

Es gelten die Rechenregeln:

Kommutativgesetz: $r\mid s = s\mid r$

Idempotenzgesetz: $r\mid r = r$

Distributivgesetz: $r(s\mid t) = rs\mid rt$ und $(s\mid t)r=sr\mid tr$

Neutrale Elemente: $r\mid\emptyset =\emptyset\mid r=r$ und $r\epsilon=\epsilon r=r$

Wir können hiermit zu jeder Grammatik einen regulären Ausdruck finden, der die gleiche Sprache erzeugt: eine Sprache aus der Sprachklasse Typ-3. reguläre Ausdrücke und reguläre Grammatiken können auf endliche Automaten reduziert werden.

Wie bereits erwähnt, werden diese regulären Ausdrücke für Suchmuster verwendet. D.h. Werkzeuge wie sed oder grep unter UNIX greifen genau auf dieses Modell zu. Die Konkatenation ($ab$), Auswahl ($a\mid b$) oder der Kleene-Stern ($*$) sind unverändert vorhanden. Alle anderen Erweiterungen dienen der Verkürzung der Schreibweise und lassen sich auf diese Kernkonstrukte zurückführen.

Die Funktion $L$, die unserem regulären Ausdruck $\alpha$ eine Sprache zuordnet wird durch folgende Gleichungen definiert, die wir auch gleich in einem Beispiel anwenden werden:

$L(\emptyset) = \emptyset$

Die vom regulären Ausdruck $\emptyset$ erzeugte Sprache ist leer (es ist das leere Wort $\epsilon$). Nicht vergessen: leere Mengen sind von Definition aus regulär.

$L(a) = \{a\}$

Die vom regulären Ausdruck $a$ erzeugte Sprache ist das Zeichen $a$.

$L(\alpha\cup\beta) = L(\alpha)\cup L(\beta)$

Die Sprache, die aus der Vereinigung von zwei regulären Ausdrücken $\alpha$ und $\beta$ beschrieben wird, kann man auch auch durch die Vereinigung der Sprachen, die nur durch $\alpha$ und $\beta$ beschrieben werden, erzeugen.

$L(\alpha\beta) = L(\alpha)\cdot L(\beta)$

Die Sprache, die aus der Konkatenation von zwei regulären Ausdrücken $\alpha$ und $\beta$ beschrieben wird, kann man auch auch durch die Konkatenation der Sprachen, die nur durch $\alpha$ und $\beta$ beschrieben werden erzeugen.

$L(\alpha^{*}) = (L(\alpha))^{*}$

Die Sprache, die durch den Sternoperator, angewandt auf den regulären Ausdruck $\alpha$ erzeugt wird, kann auch durch Anwendung des Sternoperators auf die nur durch $\alpha$ beschriebene Sprache erzeugt werden.

Am einfachsten zeigt man die Anwendung sicher an einem kleinen Beispiel (aus dem Skript).

Beispiel: regulärer Ausdruck $\beta=(\emptyset^{*}\cup(a^{*}b))$

Wir suchen also die durch den Ausdruck beschriebene Sprache $L(\beta)$. Das geht ganz simpel durch Auflösen:

$\begin{align}L(\beta)&=L((\emptyset^{*}\cup(a^{*}b)))\\&=L(\emptyset^{*})\cup L(a^{*}b)\\&=L(\emptyset^{*})\cup(L(a^{*})\cdot\{b\})\\&=\{\epsilon\}\cup(\{a\}^{*}\cdot\{b\})\\&=\{\epsilon\}\cup\{a\}^{*}\cdot\{b\}\end{align}$

Damit ist die zum regulären Ausdruck $\beta$ gesuchte Sprache $L(\beta)=\{\epsilon\}\cup\{a\}^{*}\cdot\{b\}$.

Was haben wir gemacht?

$(1)$ Auflösung von $\beta$

$(2)$ wir können nicht nur Elemente, sondern auch Mengen mit den oben genannten Operationen verbinden, was wir hier der Übersichtlichkeit halber getan haben.

$(3)$ $\{b\}$ ist nur ein einzelnes Zeichen, dass können wir ebenfalls für die Übersichtlichkeit rausnehmen und mit der Konkatenation wieder verbinden

$(4)$ welche Sprache beschreibt $L(\emptyset)$? Keine große, es besteht nur aus dem leeren Wort $\epsilon$. Gesagt, getan! Was beschreibt $L(a^*)$? Nur einen beliebig langen String aus $a's$. Also auflösen.

$(5)$ und nun das Verbliebene nur noch mit den Operatoren verbinden und wir haben unsere Sprache gefunden.

Antwort zum Lernziel: mit regulären Ausdrücken (d.h. die Verwendung von Zeichen aus dem Alphabet mit den auf regulären Mengen definierten Operationen Vereinigung, Konkatenation und Kleene Stern) beschreiben wir Erzeugungsvorschriften für reguläre Sprachen. Sie fungierten so als eine Art "Name" für eine reguläre Menge.

Lernziel 6

Was ist eine rechtslineare Grammatik?

Wie wir oben bereits geschrieben haben ist jede reguläre Grammatik auch eine rechtslineare Grammatik. Aufgrund der Struktur der Produktion neigt sich der Syntaxbaum nach rechts unten weg. Die Regeln haben folgende Form:

$A\rightarrow\omega B$ oder

$A\rightarrow\omega$

Das heißt soviel, dass die rechte Seite der Produktion aus einem Wort (mehrere Zeichen) über $\Sigma$ und einem Nonterminal oder nur einem Wort über $\Sigma$ besteht. Merkt euch die Definition, der Unterschied zur rechtslinearen Normalformgrammatik ist nur ganz klein, aber wichtig. Mit dem leeren Wort $\epsilon$ können wir ein Nonterminal verschwinden lassen und so den Ableitungsprozess stoppen.

Ein Beispiel aus dem Buch von Dirk. W. Hoffmann (auf die Definition Skript gemünzt): $G_1=(\Pi,\Sigma,R,S)$ mit $\Pi=\{S,B,C\}$, $\Sigma=\{a,b\}$, Startsymbol $S$ und den Regeln $R$:

$S\rightarrow aB$

$B\rightarrow bC$

$C\rightarrow\epsilon\mid aB$

Wollen wir z.B. $abab$ ableiten, also schauen ob $abab\in L(G_1)$ ist, so haben wir folgende Sequenz: $S\rightarrow aB\rightarrow abC\rightarrow abaB\rightarrow ababC\rightarrow abab$. Der Syntaxbaum hierzu sieht wie folgt aus:

Schaut nochmal zur Definition der Typ-3-Sprachen (erzeugt von regulären Grammatiken, damit ist jede reguläre Sprache auch rechtslinear) hoch. Unsere Grammatik $G_1$ erfüllt genau die dort gemachten Einschränkungen und erzeugt unsere Sprache. Sie ist außerdem auch noch in einer (rechtslinearen) Normalform, aber dazu gleich mehr.

Antwort zum Lernziel: eine rechtslineare Grammatik hat eine bestimmte Form der Produktionsregeln (auf der rechten Seite der Produktion steht entweder ein Wort oder ein Wort, gefolgt von einem Nonterminal). Da nur am äußersten, rechten Rand ein Nonterminal steht, dass ersetzt werden kann, neigt sich der Ableitungsbaum nach rechts.

Diese Regeln entsprechen denen für die Typ-3 Grammatiken, so dass jede reguläre Sprache auch rechtslinear ist.

Lernziel 7

Wie zeigt man, dass die reguläre Sprache von rechtslinearen Grammatiken erzeugt wird?

Eine von einer regulären Grammatik erzeugte Sprache nennt man reguläre Sprache. Für jede reguläre Sprache existiert auch immer mindestens eine reguläre Grammatik. Wir müssen also zeigen, dass wir aus einer rechtslinearen Grammatik mit den bei Typ-3-Definition gemachten Einschränkungen eine reguläre Sprache erzeugen können.

Die Beweisidee im Skript folgt der Induktion über den Aufbau regulärer Mengen mittels der Operationen Vereinigung, Produkt und Stern aus den Mengen $\emptyset$ und $\{a\}$ über einem Alphabet $\Sigma$. Es wird gezeigt, dass es zu diesen Mengen rechtslineare Grammatiken gibt. Wenn das der Fall ist, so gibt es auch (aufgrund der Abgeschlossenheit) auch rechtslineare Grammatiken zu den Ergebnissen wenn man Vereinigung, Produkt und Stern auf $\emptyset$ und $\{a\}$ anwendet.

Ohne auf Details einzugehen:

1. Wir zeigen, dass wir die Sprachen $L_1=\emptyset$ und $L_2=\{a\}$ durch entsprechende Grammatiken $G_1$ und $G_2$ erzeugen können

2. Anschließend zeigen wir, dass wir durch die Vereinigung $L_1\cup{L_2}$ eine neue Sprache $L$ bekommen, die wir wiederum durch eine entsprechende Grammatik $G$ erzeugen können

3. Nun kümmern wir uns um das Produkt $L_1\cdot{L_2}$ und zeigen ebenfalls, dass wir zu der erzeugten Sprache $L$ eine Grammatik $G$ angeben können, die $G$ erzeugt

4. Und als letztes das Gleiche mit dem Sternoperator: $L={L_1}^{*}$

Damit erzeugen rechtslineare Grammatiken mindestens alle regulären Sprachen.

Antwort zum Lernziel: mittels der Operationen Kleene Stern, Vereinigung und Konkatenation können wir aus den Mengen $\emptyset$ und $\{a\}$ weitere reguläre Mengen erzeugen. Diese werden anschließend mittels passender Grammatik, die den "rechtslinearen Einschränkungen" unterliegt erzeugt.

Da wir mit den drei Operationen alle regulären Mengen abbilden können und für alle dadurch erzeugten, neuen Mengen rechtslineare Grammatiken angegeben haben, können wir so sagen, dass alle regulären Sprachen von rechtslinearen Grammatiken erzeugt werden.

Lernziel 8

Wie transformiert man eine rechtslineare Grammatik in eine rechtslineare Normalform?

Zunächst: was ist eine Normalform? Im Prinzip ist es eine Vereinfachung durch Umformung. In einer rechtslinearen Normalformgrammatik haben alle Regeln die Form:

$A\rightarrow aB$ oder

$A\rightarrow\epsilon$

D.h. dass einem Terminalsymbol (kann nicht weiter ersetzt werden, hier $a$) immer ein Nonterminalsymbol (kann weiter ersetzt werden, hier $A$ und $B$) folgt. Die Nonterminale können also nur ersetzt werden durch ein leeres Wort $\epsilon$ oder durch die Kombination eines Terminalsymbols mit einem Nonterminalsymbol.

Und jetzt schaut einmal kurz hoch zur Definition der rechtslinearen Grammatik: ist euch der Unterschied aufgefallen? Anstatt, dass die rechte Seite der Produktion auch Wort $\omega$ erlaubt, erlaubt uns die Normalform nur ein einziges Terminalzeichen, d.h. nur noch ein Symbol $a$ auf rechten Seite. Damit werden alle Wörter in regulären Grammatiken in Normalform immer nach dem selben Prinzip erzeugt: ausgehend vom Startsymbol wird jede Produktion immer ein Zeichen anfügen und ein Nichtterminal ersetzen. Wir verlängern die Zeichenkette in einem Ableitungsschritt immer nur um ein Zeichen und begrenzen es durch ein immer wechselndes Nonterminal.

Um also eine rechtslineare Grammatik in eine rechtslineare Normalform zu transformieren werden die Terminalregeln so angepasst, dass die Grammatik terminiert, die Regeln verkürzt und so alle Regeln eliminiert, die nicht der Normalform entsprechen (d.h. es kommt keine Regel der Forml $A\rightarrow B$ (Nonterminal zu Nonterminal, Platzhalter zu Platzhalter) vor).

Und jetzt kommt der Grund, warum ich die Kurseinheit 5 so gerne mag: ein sehr ausführliches Beispiel dieser einer Transformation, dass ich hier auch gerne ausführen würde:

Beispiel: $G=(\Pi,\Sigma,R,S)$ mit

$\Pi=\{S,A,B,C\}$ (unsere Nonterminale)

$\Sigma=\{a,b\}$ (unsere Terminale)

und folgenden Regeln $R$:

$S\rightarrow A$

$S\rightarrow B$

$A\rightarrow C$

$A\rightarrow aB$

$A\rightarrow baaB$

$B\rightarrow A$

$B\rightarrow bbC$

$C\rightarrow a$

Man sieht gleich, dass das wir hier einige Regeln haben, die nicht der Normalform entsprechen. Die müssen wir nun loswerden.

1. Der Übersicht halber wird mit $\mid$ abgekürzt:

$S\rightarrow A\mid B$

$A\rightarrow C\mid aB\mid baaB$

$B\rightarrow A\mid bbC$

$C\rightarrow a$

2. Nun kümmern wir uns um die korrekte Terminierung, d.h. $G$ muss die Möglichkeit bieten ein Nichtterminal durch ein leeres Wort  $\epsilon$ zu ersetzen. Wie man sieht, ist das bei unseren Regeln nicht der Fall. Wir fügen also eine neue Regel ein und passen die letzte Regel an damit die Terminierung auch erreichbar ist:

$S\rightarrow A\mid B$

$A\rightarrow C\mid aB\mid baaB$

$B\rightarrow A\mid bbC$

$C\rightarrow aE$

$E\rightarrow\epsilon$

3. Nun werden die Regellängen verkürzt. Wir haben einige Regeln, die bestehen aus mehr Terminalen als für die Normalform notwendig. Wir verkürzen also die Regeln $A\rightarrow baaB$ und $B\rightarrow bbC$ in jedem Schritt um ein Terminalsymbol indem wir ein neues Nonterminal einführen. Das wird solange fortgeführt bis wir in unserer Normalform landen:

$A\rightarrow baaB$ wird zu

$A\rightarrow bX$ und

$X\rightarrow aaB$

Letzteres wird dann weiter transformiert zu

$X\rightarrow aY$ und

$Y\rightarrow aB$

Länge erreicht. Das Gleiche wird mit $B\rightarrow bbC$ durchgeführt und wir kommen insg. zu:

$S\rightarrow A\mid B$

$A\rightarrow C\mid aB\mid bX$

$X\rightarrow aY$

$Y\rightarrow aB$

$B\rightarrow A\mid bZ$

$Z\rightarrow bC$

$C\rightarrow aE$

$E\rightarrow\epsilon$

4. Jetzt werden nur noch die Regeln eliminiert, die auf Nonterminale zeigen (d.h. in der Form $S\rightarrow A$). Dazu ersetzen wir einfach das zu eliminierende Nonterminal durch seine "Ersatzzeichenkette". Auf der rechten Seite der Produktionen haben wir die Nonterminale $A,B$ und $C$, die wir ersetzen müssen. Wir fangen zunächst mit $A$ an und ersetzen es durch seine "Ersatzzeichenkette" $C\mid aB\mid bX$ in den Regeln $S$ und $B$.

$S\rightarrow C\mid aB\mid bX\mid B$

$A\rightarrow C\mid aB\mid bX$

$X\rightarrow aY$

$Y\rightarrow aB$

$B\rightarrow C\mid aB\mid bX\mid bZ$

$Z\rightarrow bC$

$C\rightarrow aE$

$E\rightarrow\epsilon$

Nun kümmern wir uns um $B$ und ersetzen es durch seine "Ersatzzeichenkette" $C\mid aB\mid bX\mid bZ$ in seinem einzigen Vorkommen in $S$:

$S\rightarrow{C\mid aB\mid bX\mid C\mid bZ}$

$A\rightarrow C\mid aB\mid bX$

$X\rightarrow aY$

$Y\rightarrow aB$

$B\rightarrow{C\mid aB\mid bX\mid bZ}$

$Z\rightarrow bC$

$C\rightarrow aE$

$E\rightarrow\epsilon$

Fehlt nur noch $C$, dass überall auf der rechten Seite der Produktionen durch $aE$ ersetzt wird und wir haben am Ende eine rechtslineare Normalform:

$S\rightarrow aE\mid aB\mid bX\mid bZ$

$A\rightarrow aE\mid aB\mid bX$

$X\rightarrow aY$

$Y\rightarrow aB$

$B\rightarrow aE\mid aB\mid bX\mid bZ$

$Z\rightarrow bC$

$C\rightarrow aE$

$E\rightarrow\epsilon$

Antwort zum Lernziel: bei einer rechtslinearen Grammatik gilt nur die Einschränkungen $A\rightarrow\omega B$ oder $A\rightarrow\omega$. D.h. die rechte Seite der Produktion muss aus einem Wort, welches mit einem Nonterminal abschließt oder nur durch ein Wort bestehen. Bei der zugehörigen Normalform ist das nicht mehr erlaubt. Dort gelten nur noch die Regeln $A\rightarrow aB$ sowie die Abschlussregel $B\rightarrow\epsilon$.

Durch Verkürzung der Produktionen, eine korrekte Terminierung mit $\epsilon$, Eliminierung der Regeln, die nicht dem genannten Schema für die Normalform entsprechen können wir so eine rechtslineare Grammatik in eine Normalform überführen.

Und das war auch schon KE5. Wie immer gilt: Wer Fehler oder Ungenauigkeiten findet, ab in die Kommentare oder per Mail.

Lernziel 3

Wie ist der Vollständigkeitsbeweis zu $SAT$?

$SAT$ steht für das englische satisfiability. Also ein Erfüllbarkeitsproblem. Es wird gefragt ob eine aussagenlogische Formel erfüllbar ist (erinnert ihr euch an KNF/DNF aus der technischen Informatik? Das hier ist nicht weit weg...).

Da eine Formel nur endlich viele variablen enthält, die nur mit $1$ und $0$ belegt werden können, haben wir eine endliche Anzahl an Möglichkeiten. Wenn wir alle durchprobieren, kommen wir (oder nicht) irgendwann dahin, dass die Formel wahr wird. Haben wir $n$ Variablen, so müssen wir im worst case $2^n$ Kombinationen betrachten. Damit benötigen wir für $SAT$ einen Exponentialzeitalgorithmus und diese gelten für die Praxis als unwichtig, steigt der Aufwand für größere $n$ doch massiv an. Hätten wir zu dem Problem einen Polynomialzeitalgorithmus, sähe die Sache ganz anders aus.

Aber es gibt einen Lichtblick: Wenn wir nicht jede Möglichkeit durchprobieren wollen, kann das Prüfen einer vorgegebenen Lösung für $SAT$ in Linearzeit erfolgen. Haben wir $n$ Variablen, so müssen wir sie erst kurz belegen und die Formel dann auswerten. Beides geht jeweils in Linearzeit. Damit haben wir schon einmal den ersten Schritt getan: wir haben eine $KTM$ angegeben, die die Hilfseingabe (unsere zu prüfende Belegung der $n$ Variablen) auf wahr oder falsch kontrolliert. Okay, haben wir nicht. Aber wir könnten es mit wenig Aufwand (vielleicht reiche ich so eine $KTM$ bei Gelegenheit hier nach) tun. Damit ist der erste Schritt vollbraucht $SAT\in NP$.

Kümmern wir uns nun um den zweiten Schritt, die $NP$-Härte. Aber ohne die Abkürzung der Reduktion zu nehmen. Das folgende Beispiel basiert auf dem Buch von Prof. Dr. Dirk W. Hoffmann (oben rechts verlinkt). Die Credits also ausnahmslos an ihn. Und auch wenn ich mich wie eine kaputte Schallplatte anhöre: das Buch ist ein Lifesaver für theoretische Informatik und gehört in jedes IT-Bücherregel, daher absolute Kaufempfehlung. Der Herr gehört unbedingt unterstützt.

Wir müssen hier also beweisen, dass wir ausnahmslos alle Probleme aus $NP$ auf $SAT$ reduzieren können. Da wir keines haben, müssen wir uns eins basteln, wo einzusehen ist, dass es alle Probleme aus $NP$ "widerspiegelt" und dieses auf $SAT$ reduzieren. Nehmen wir also ein beliebiges Problem $L\in NP$ und eine $TM$ namens $T$, die das Problem entscheidet. Wir müssen jetzt zeigen, dass wir für jedes Eingabewort $\omega$ für $T$ eine Formel $F$ konstruieren können, für die gilt:

$T(\omega)$ terminiert im Endzustand $\Leftrightarrow F(\omega)$ ist erfüllbar.

D.h. nur wenn unsere Maschine mit dem Eingabewort terminiert, so ist auch unsere Formel mit dem gleichen Eingabewort erfüllbar und andersrum. Wir müssen $F$ in polynomieller Zeit konstruieren. Dazu werden zunächst Variablen eingeführt:

$B_{i,k,\sigma}=1$ Nach $i$ Schritten, steht an Position $k$ das Zeichen $\sigma$.

$S_{i,S}=1$ Maschine $T$ befindet sich nach $i$ Schritten im Zustand $S$.

$P_{i,k}=1$ Maschine $T$ befindet sich nach $i$ Schritten auf Bandposition $k$.

Die Laufzeit der Maschine ist polynomiell durch das Polynom $p(n)$ beschränkt, denn $n$ ist die Länge der Eingabe $\omega$. Die Indizes von $i,s$ liegen also im Intervall $[0;p(n)]$. Auch bewegt sich der Schreib-Lese-Kopf maximal $p(n)$ Positionen nach links oder rechts, so dass wir den Bandinhalt auf dem Teilstück $-p(n),...,p(n)$ betrachten müssen. Der Kopf steht über der Position $0$. Ausprobiert wird das an der Sprache $L:=\{\#^n\mid n\in{\mathbb{N}}\}$ mit dem Alphabet $\Sigma=\{\#\}$.

Diese Sprache wird von einer $TM$ erkannt, die nur zwei Zustände hat. $s_0$ wenn das Zeichen auf dem Band eine $\#$ ist (Eingabewort $\omega\in L$) und $s_1$ wenn es ein $B$ (Blank) ist. Da die Berechnung hier bereits nach einem Schritt endet, ist die Laufzeit der Maschine $p(n)=1$. Wir haben also ein "Problem", dass in polynomieller Zeit durch die $T$ entschieden werden kann und damit in $P$ liegt (das $N$ ist ja nur das Orakeln der Eingabe). Nun müssen wir $T$ nur noch polynomiell in eine $SAT$-Instanz codieren.

Um den Bandzustand, den Zustand der Maschine und die Position des Lesekopfes als eine Formel zu codieren, werden die oben eingeführten Variablen verwendet. Ist z.B. $B_{0,1,\#}=1$, so befindet sich auf dem Band jetzt auf Position $1$ das Zeichen $\#$. Durch die oben gemachten Einschränkungen, haben wir $12$ verschiedene Bandvariablen, die wir mit $0$ oder $1$ belegen können um den Bandzustand zu repräsentieren ($B$ ist das Blank).

$B_{0,-1,B},B_{0,-1,\#},B_{1,-1,B},B_{1,-1,\#}$

$B_{0,1,B},B_{0,1,\#},B_{1,1,B},B_{1,1,\#}$

$B_{0,0,B},B_{0,0,\#},B_{1,0,\#},B_{1,0,\#}$

Der Zustand von $T$ codieren wir mit:

$S_{0,S_0},S_{0,S_1},S_{1,S_0},S_{1,S_1}$

Für die Kopfposition haben wir sechs Variablen:

$P_{0,-1},P_{0,0},P_{0,1}$

$P_{1,-1},P_{1,0},P_{1,1},$

Mit diesen Variablen haben wir alle Variablen repräsentiert, die die Maschine $T$ einnehmen kann. Wenn wir die Maschine also in $SAT$ abbilden wollen, sieht die Formel $F$ dann so aus:

$F=S\wedge R\wedge T\wedge A$

Was bedeutet es?

$S$: Startbedingung. Initiale Konfiguration von $T$. Die Maschine befindet sich in $s_0$, das Eingabewort $\omega$ ist auf dem Band, der Rest ist leer und der Kopf befindet sich auf Position $0$.

$R$: Randbedingungen, die $T$ zu jeder zeit erfüllen muss, d.h. $R=(R_1\wedge R_2\wedge R_3)$ Diese sind:

$R_1$: Maschine befindet sich zu jedem Zeitpunkt in nur einem Zustand

$R_2$: Der Schreib-Lese-Kopf befindet sich immer nur an einer Position.

$R_3$: Es befindet sich nur ein Symbol an jeder Bandstelle zu jedem Zeitpunkt.

$T$: Transitionsbedingungen. In dieser Teilformel werden die möglichen Konfigurationsübergänge codiert, d.h. $T=(T_1\wedge T_2\wedge T_3)$ Sie bestehen aus:

$T_1$: Maschine geht in Folgekonfiuration über.

$T_2$: Inaktive Maschine, terminiert.

$T_3$: Bandinhalt wird geändert.

$A$: Akzeptanzbedingung. Hier wird codiert, dass die $TM$ das Wort $\omega$ dann annimmt wenn es im Endzustand anhält. Der Zustand muss in weniger als $p(n)$ Berechnungsschritten erreicht werden.

Und nun kommt der Spaß an der Sache. Alle Bedingungen können wir als Formel codieren.

Beispiel: nehmen wir an, das Wort $\omega$ besteht aus $\#$, d.h. auf dem Band steht $B\# B$. Die oben in Prosa verfasste Startbedingung, wäre dann:

$S=S_{0,s_0}\wedge{P_{0,0}}\wedge{B_{0,-1,B}}\wedge{B_{0,0,\#}}\wedge{B_{0,1,B}}$

In Worten ausgedrückt: Die Maschine befindet sich nach $0$ Schritten im Zustand $s_0$ (erste Bedingung), der Lesekopf nach $0$ Schritten auf Position $0$ (zweite Bedingung) und auf dem Band steht auf Positionen $-1,0,1$ eben $B,\#,B$ (dritte, vierte und fünfte Bedingung). Und wenn das alles stimmt, die Variablen also alle mit einer $1$ belegt sind, dann evaluiert die Formel $S$ bei Auswertung zu $1$. Oh mein Gott! Das ist genau das, was wir für die Maschine $T$ festgelegt und nun in eine Formel gequetscht haben.

Haben wir z.B. ein leeres Wort $\epsilon$, d.h. auf dem Band steht $BBB$, so sieht unsere Startbedingung wie folgt aus:

$S=S_{0,s_0}\wedge{P_{0,0}}\wedge{B_{0,-1,B}}\wedge{B_{0,0,B}}\wedge{B_{0,1,B}}$

Gleiches gilt für Rand-, Transitions- und Akzeptanzbedingungen, die wir eben auch als Formel darstellen können. Ist nur alles ziemliche Schreibarbeit. Wenn die alle erfüllt sind, evaluiert auch unsere Gesamtformel $F$ (siehe oben) zu einer $1$. Eventuell schreibe ich die kompletten Rand- und Transitionsbedingungen bei Gelegenheit hier nochmal hin.

Wie wir also sehen können, können wir die Bedingungen für eine Maschine $T$ in eine Formel $F$ quetschen, die genau das tut, was wir wollen. Wir haben also gezeigt, wie eine $NTM$ $T$ polynomiell auf eine aussagenlogische Formel reduziert werden kann, die genau dann erfüllbar ist, wenn $T$ in einem Endzustand terminiert.

Ein ausführlicher Beweis ist z.B. auch hier zu finden.

Hier entfaltet $SAT$ seinen Charme: wir können viele Algorithmen auf $SAT$ zurückführen, indem wir den Ablauf in die Formel hineincodieren und damit das Problem auf $SAT$ reduzieren. Und was passt hier besser als Beispiel, als $3SAT$?

Antwort zum Lernziel: wir codieren eine komplette Aussagenlogische Formel in ein Wort für eine Turingmaschine, deren Laufzeit polynomiell beschränkt ist. Die Maschine terminiert nur wenn die aussagenlogische Formel wahr ist. Es ist leicht einzusehen, dass diese initiale Turingmaschine, also praktisch unser $NP$-vollständiges Problem (wo leicht einzusehen ist, dass es tatsächlich in $NP$ liegt), in polynomzeit durch eine Kontroll-Turingmaschine entschieden werden kann.

In die Eingabe dieser Maschine dieses wird dann die zu prüfende, aussagenlogische $SAT$-Formel codiert und von dieser $KTM$ ebenfalls in Polynomzeit entschieden.

Lernziel 4

Wie führt man eine einfache, polynomielle Reduktion ${}\leq_{pol}$  aus?

Reduktion von $SAT$ auf $3SAT$

Die Frage bei $3SAT$ ist:

Gibt es eine erfüllende Bedingung bei $n$ aussagenlogischen Klauseln mit maximal $3$ Literalen (atomare Aussage, z.B. $\neg{A}$ oder $A$)?

Damit ist $3SAT$ eine abgeschwächte Form von $SAT$. Einschränkung ist, dass die Formel für $3SAT$ in der Konjunktivform (mit $\wedge$ verknüpft) vorhanden sein muss. Um also zu zeigen, dass $3SAT$ ebenfalls $NP$-hart ist, müssen wir $SAT$ auf $3SAT$ polynomiell reduzieren, formal ausgedrückt:

$SAT\leq_{pol}3SAT$

Was wir tun müssen, ist also eine allgemeine Formel nehmen und sie so umformen, dass die beliebig viele Klauseln, aber nur drei Literale pro Klausel hat. Das machen wir mit Hilfe von Hilfsvariablen. Haben wir also ein Term in der folgenden Form in KNF mit $n$ Variablen:

$(\upsilon_{1,1}\vee\upsilon_{1,2}\vee ...\vee\upsilon_{1,n})\wedge(\upsilon_{m,1}\vee\upsilon_{m,2}...\vee\upsilon_{m,n_{m}})$

Für jede Klausel mit $n$ Variablen entstehen $n-2$ neue Klauseln mit $n-3$ neuen Variablen:

$(\upsilon_{1,1}\vee\upsilon_{1,2}\vee a_{1,1})\wedge(\overline{a_{1,1}}\vee\upsilon_{1,3}\vee a_{1,2})\wedge ...\wedge(\overline{a_{1,n-3}}\vee \epsilon_{1,n_{1}-1}\vee\epsilon_{1,n_{1}})$

Hilfsvariablen? Ja, Hilfsvariablen. Diese Variablen zeigen uns an, welcher Teil aus der zerteilen Klausel das ganze Konstrukt hat wahr werden lassen.

Beispiel? Klar: $(A\vee\overline{B}\vee C\vee\overline{D})\wedge(E\vee F\vee G)$

Die erste Klausel wandeln wir also um in $2$ Klauseln mit einer neuen Variable. Die zweite Klauseln können wir so lassen, da wir da bereits drei Literale drin haben. Nennen wir unsere neue Hilfsvariable also einfach $h_1$. Damit sehen unsere beiden neuen Klauseln nun so aus:

$(A\vee\overline{B}\vee h_1)\wedge(C\vee\overline{D}\vee\overline{h_1})$

Der Trick hierbei ist, dass die Hilfsvariable $h_1$ dann falsch wird, wenn die erste Teilklausel wahr wird und wahr wird wenn die zweite Teilklausel wahr wird. Stellen wir doch eine kleine Wertetabelle für den umgeformten Term zusammen, wie wir das auch in der technischen Informatik (Computersysteme 1&2) gemacht haben:

Ich habe Excel etwas vergewaltigt, nehmt mir das nicht übel. Die Spalten haben folgende Bedeutung:

• In den Spalten A-D stehen alle unsere Variablenbelegungen $A,B,C,D$.
• In Spalte E steht die umzuformende Klausel $(A\vee\overline{B}\vee C\vee\overline{D})$.
• In Spalte F steht die so entstandene erste Teiltklausel,
• In G die zweite.
• In Spalte H steht unsere Hilfsvariable $h_1$, die falsch wird wenn die erste Teilklausel in Spalte F wahr ist und wahr wird wenn die zweite Teilklausel in Spalte G wahr wird. Der Inhalt von $h_1$ spielt keine Rolle wenn die Klausel sowieso negativ werden würde (grünes Kästchen).
• In Spalte I und J stehen unsere neuen Teilklausen mit der Hilfsvariable, die wir dann verwenden um die alte Klausel zu repräsentieren.
• Spalte K beherbergt dann beide Klauseln aus I und J mit einem $\wedge$ verknüpft. Genau diese Klausel
• in Spalte K ist dann: $((A\vee\overline{B}\vee h_1)\wedge(C\vee\overline{D}\vee\overline{h_1})$

Und sie tut genau das gleiche wie die initiale Klausel aus den vier Literalen, die wir umformen wollten: $(A\vee\overline{B}\vee C\vee\overline{D})$. Lange Rede, kurzer Sinn:

$(A\vee\overline{B}\vee C\vee\overline{D})$ $\Leftrightarrow$ $((A\vee\overline{B}\vee h_1)\wedge(C\vee\overline{D}\vee\overline{h_1})$

Klauseln mit nur einem Literal bekommen zwei Hilfsvariablen, Klauseln mit zwei Literalen eine, Klauseln mit drei Literalen werden nicht angefasst und Klauseln mit mehr als drei Literalen werden nach dieser Vorgehensweise rekursiv in Klauseln mit drei Literalen umgewandelt. Die Anzahl der Literale hat sich also nur linear erhöht und wir haben einen Weg gefunden $SAT$ auf $3SAT$ in Polynomzeit zu reduzieren. Nun können wir auch $3SAT$ für andere Schweinereien benutzen!

Antwort zum Lernziel: am beispiel von $3SAT$ sehen wir die Reduktion, indem wir eine aussagenlogische Formel so umformen, dass wir zwar beliebig viele Klauseln, aber nur drei Literale pro Klausel haben. Schaffen wir diese Reduktion in Polynomzeit durchzuführen, so ist sie uns gelungen.

Lernziel 5

Angabe einiger NP-vollständigen Probleme

Im Skript werden noch weitere Probleme besprochen, die $NP$-vollständig sind. Zwei davon sind $CLIQUE$ und $IND\_SET$. Fangen wir doch zunächst mit $CLIQUE$ an. Definition (erneut geklaut aus dem Buch von Hr. Hoffmann):

Graph $G$ mit Knotenmenge $V$ und Kantenmente $E$

Fragestellung: Existieren $n$ Knoten $v_1,...,v_n$, die paarweise durch eine Kante aus $E$ verbunden sind?

Menge $C=\{v_1,...,v_n\}$ mit dieser Eigenschaft heißt $CLIQUE$ der Größe $n$

In klaren Worten ist eine $CLIQUE$ eine Menge von Knoten, die alle miteinander verbunden sind.

Beispiel: $G_1$ mit

$V_1=\{1,2,3,4,5,6\}$ und

$E=\{\{1,2\},\{1,3\},\{2,3\},\{2,4\},\{2,5\},\{4,5\},\{5,6\},\{6,3\},...\}$ (die Kanten in die andere Richtung habe ich aus Faulheit ausgelassen, denkt sie euch einfach dazu)

Hier haben wir Cliquen mit den Knoten $\{1,2,3\},\{2,4,5\},\{2,3,5\},\{3,5,6\}$ identifiziert. Um zu beweisen, dass wir eine Clique der Größe $n$ gefunden haben, müssen wir nur eine geeignete Knotenmenge raten und prüfen ob paarweise durch eine Kante verbunden sind. Raten wir z.B. $C=\{1,5,6\}$, müssen wir auf folgende Kanten prüfen: $\{1,5\},\{1,6\},\{5,1\},\{5,6\},\{6,1\},\{6,5\}$. Jaja, ungerichteter Graph, ich weiß: ein vorhandener Weg von $A$ nach $B$ impliziert den Weg von $B$ nach $A$. Aber wir tun uns mit der Prüfung aller Möglichkeiten nicht weh, da dieser sowieso polynomiell beschränkt bleibt. So können wir aber auch ungerichtete Graphen in die Betrachtung mit einbeziehen.

Liegen die Kanten also in unserer Menge $E$, so haben wir eine Clique gefunden. Man sieht leicht, dass mit der zu suchenden Cliquen-Größe der Aufwand, d.h. die Anzahl der zu prüfenden Kanten, quadratisch ($n^2$) in Abhängigkeit von $n$ zunimmt. Da wir eine Lösung raten und sie mit quadratischem Aufwand prüfen können, liegt unsere $CLIQUE\in NP$ .

Jetzt kümmern wir uns um den aufwendigeren Teil, die $NP$-Härte von $CLIQUE$. Dazu reduzieren wir einfach $3SAT$ auf $CLIQUE$. Wir müssen also eine Formel $M$ konstruieren, dass gilt:

$M$ ist erfüllbar $\Leftrightarrow G$ enthält eine Clique der Größe $n$

Achtung: wir verfolgen den Weg von einer Formel zum Graphen und nicht anders herum. Wir überführen also eine Formel, die wahr wird wenn sie eine Belegung hat in einen Graphen, der genau bei dieser Belegung eine Clique hat. Machen wir das am besten an einem Beispiel:

Beispiel: $(A)\vee(\neg{A}\wedge{B})\vee(\neg{A}\wedge{C})$

Wie basteln wir uns daraus einen Graphen? Nach folgenden Regeln:

• Jedes Literal wird ein Knoten
• Zwischen jedem Knoten gibt es eine Kante wenn
  • sie nicht in der selben Klausel stehen und
  • wenn sie gleichzeitig erfüllbar sind ($A$ und $\neg{A}$ sind z.B. nicht gleichzeitig erfüllbar)

Ganz einfach. Um es deutlicher zu machen, beschriften wir die Knoten mit $i,j$. $i$ ist die Nr. der Klausel und $j$ die Nummer des Literals in der Klausel. Z.B. wäre der Knoten, der das Literal $A$ in der ersten Klausel beschreibt, beschriftet mit $(1,1)$.

Mit den Knoten können wir auch direkt eine Belegung für die Formel ableiten, die sie wahr werden lässt: $A=B=C=1$. Wäre ein Knoten negativ, so würden wir das Literal ${}=0$ setzen. Probiert es mal selbst an der folgenden Wertetabelle aus und bastelt euch eine Formel und den dazugehörigen Graphen

Übung:

[spoiler]  (mehr …)

Update: Antworten zu den Lernzielen hinzugefügt.

Nach dieser Kurseinheit haben wir mehr als die Hälfte des Weges geschafft und das Licht am Ende des Tunnels ist schon sichtbar. Hoffen wir, dass es kein Zug ist.

Die Grundlagen des Beweises der Vollständigkeit einer Menge haben wir bereits in diesem Beitrag skizziert. Dass der Beweis nicht unbedingt schwierig ist wenn bereits ein Problem als $NP$-vollständig bewiesen ist und wir eine Reduktion durchführen können, haben wir bereits gelernt. Schwieriger ist es jedoch die $NP$-Vollständigkeit ohne diese Reduktion von einer bereits bekannten Menge zu beweisen. Wir wenden uns in diesem Beitrag den zwei Problemen aus dem Skript zu und tun dies.

Lernziel 1

Wie ist der Vollständigkeitsbeweis zu 2D-DOMINO?

Bevor diese Frage beantworten: Was ist $2D-Domino$? Es wird auch als Kachelproblem bezeichnet. Unter diesem Namen findet sich auch in der Literatur eine Erklärung, wer mit der Beschreibung aus dem Skript nicht weiterkommt. Im Grunde geht es um die vollständige Belegung des Spielbretts nach bestimmten Regeln. Aber fangen wir erstmal klein an und zerlegen die Definition aus dem Skript:

$N\in\mathbb{N}$

Das ist die Größe des quadratischen Brettes. Ist $N := 4$, so ist unser Spielbrett $4x4$ Felder groß.

$S\subseteq{({\{0,1\}}^{+})}^4$

Damit bezeichnen wir den Satz unserer Spielsteine. Ein Spielstein ist gegeben durch ein Quintupel: $(L,R,O,U)\in{({\{0,1\}}^{+})}^4$. Nehmen wir an, dass wir z.B. $S=\{\{0,0,0,0\},\{0,0,0,1\}\}$ als Steinsatz haben, so befinden sich in unserem Satz zwei Steine: einer hat gar keine Markierung und einer nur unten (siehe nächste Abbildung).

Update: Barbara hat mich hier auf etwas hingewiesen. $(L,R,O,U)\in{({\{0,1\}}^{+})}^4$ bedeutet, dass wir $L,R,O,U$ als Worte über ${\{0,1\}}^{+}$ codieren können. D.h. wir können z.B. auch einen einzelnen Stein mit $\{1011,1111,1000,0001\}$ abbilden. Die einzelnen Elemente für $L,R,O,U$ bezeichnen dann die Farbe links, rechts, oben oder unten im Stein. Bei einem Wort mit der Länge $4$ haben wir somit $2^4=16$ verschiedene Farben, die wir nutzen können.

Bei $4$ Feldern auf dem Stein, die jeweils mit $16$ unterschiedlichen Farben codiert werden können, haben wir also $16^4=65536$ unterschiedliche Möglichkeiten einen Stein zu codieren.

Ich bin aber eine faule Sau und habe nur die Farben Schwarz und Weiß zugelassen um eine kleinere Menge an Steinen zu haben. Das habe ich nicht so konkret aufgeführt, wie ich das eig. gedacht habe. Dem Beispiel tut das aber keinen Abbruch. Daher schränke ich für mein Beispiel die Menge der Steine hier (im Gegensatz zum Skript, bitte daher also nicht vergessen: im Skript sind die Farben codiert mittels einem Wort über ${\{0,1\}}^{+}$) ein auf: $(L,R,O,U)\in({\{0,1\}}^{1})^4$

Die folgende Abbildung zeigt alle $2^4$ Möglichkeiten für die Belegung der Steine, d.h. wir haben insg. 16 Steine in unserer Menge $S$.

Kommen wir zur Anfangsbelegung:

$\alpha: \{1,...,N\}^2\rightarrow S\cup\{\varepsilon\}$

Mit $\alpha$ bezeichnen wir die Anfangsbelegung eines Feldes auf dem Brett. Hat unser $4x4$ Brett z.B. die ersten Beiden Felder mit einem vollständig weißen und einem vollständig schwarzen Stein belegt, während alle anderen leer sind, so wäre $\alpha(1,1) = (0,0,0,0)$, $\alpha(1,2) = (1,1,1,1)$ und der Rest der Felder ${}=\varepsilon$. Das alles kommt in unser $D$, d.h. als $D$ bezeichnen wir das gesamte Spiel mit: $D = (N,S,\alpha)$.

$\beta: \{1,...,N\}^2\rightarrow S$

Hier haben wir eine konkrete Belegung eines Feldes. Bitte beachten, dass die Belegung das leere Feld $\varepsilon$ nicht mehr mit einschließt. $D$ ist lösbar wenn wir die Anfangsbelegung auf dem Feld belassen und die restlichen leeren Felder nach folgenden Regeln belegen:

$(\beta(i,j) = (l,r,o,u)\land\beta(i,j+1) = (l^{'},r^{'},o^{'},u^{'}))\Rightarrow r=l^{'}$ und

$(\beta(i,j) = (l,r,o,u)\land\beta(i+1,j) = (l^{'},r^{'},o^{'},u^{'}))\Rightarrow u=o^{'}$

Kleiner Klopper. Sagt aber nichts anderes aus, als dass zwei Steine zueinander passen müssen. Der linke und rechte Stein müssen bei der jeweils zueinander liegenden Seite eine Markierung aufweisen. Das Gleiche gilt für den oberen und unteren Stein. Beispiel? Klar doch.

Wir sehen hier zwei Spielfelder mit $N=3$. Das 1. Spielfeld hat die Belegung:

$\beta(1,2) = (1,0,0,0)$, $\beta(1,3) = (0,1,0,1)$ und $\beta(2,3) = (1,1,1,0)$. Folgt daraus, dass $r=l^{'}$ und $u=o'$ wie oben angegeben? Versuchen wir es:

$(\beta(1,2) = (1,0,0,0)\land\beta(1,3) = (0,1,0,1))\Rightarrow 0=0$ und

$(\beta(1,3) = (0,1,0,1)\land\beta(2,3) = (1,1,1,0))\Rightarrow 1=1$

Sieht gut aus. Nun für Spielbrett Nr. 2 mit Belegung: $\beta(1,2) = (1,0,0,0)$, $\beta(1,3) = (1,1,0,0)$ und $\beta(2,3) = (1,1,1,0)$

$(\beta(1,2) = (1,0,0,0)\land\beta(1,3) = (1,1,0,0))\Rightarrow 0=1$ und

$(\beta(1,3) = (1,1,0,0)\land\beta(2,3) = (1,1,1,0))\Rightarrow 0=1$

Ne, hier klappt das leider nicht. Damit ist die angegebene Belegung bei Spielbrett 2 nicht zulässig. Das war es auch schon. Klingt spannend. Wollt Ihr das mal spielen? Bitte sehr: Tetravex. Zumindest ist das Browsergame unserem sehr ähnlich. Nur sind hier die Steine (die Menge $S$) hier vorgegeben und nicht nur eine Zeile des Bretts belegt.

Fragestellung: Wir suchen daher nach einer korrekten Belegung für ein Spielbrett. Es ist schnell einzusehen, dass das Spiel in $NP$ liegt: wir können eine Codierung angeben und diese dann in polynimieller Zeit auf Korrektheit testen. Dazu müssen wir nur eine Kontrollturingmaschine ($KTM$) angeben, die eine von uns gegebene Hilfseingabe auf Richtigkeit testet. Um die Belegung zu raten, verwenden wir eine $NTM$.

Der Beweis der $NP$-Vollständigkeit des Dominospiels

Wir haben hier zwei Dinge zu zeigen: $2D-DOMINO\in NP$ und anschließend die $NP$-Härte indem wir ein vollständiges Problem aus $NP$ auf unseres reduzieren. Haben wir keines, so müssen wir den mühsamen Weg selbst gehen und verzichten auf die Reduktion und beweisen die $NP$-Härte direkt. Aber kümmern wir uns zunächst um Punkt 1: $2D-DOMINO\in NP$. Dazu reicht es eine $KTM$ (oder $NTM$) anzugeben, die eine Hilfseingabe in Polynomzeit auf Korrektheit prüft (eine $NTM$ rät diese Hilfseingabe auch noch von alleine).

Um eine $NTM$ anzugeben, müssen wir zunächst das Spiel so formalisieren dass wir die Anfangsbelegung und unsere Steinchen auf das Eingabeband codieren. Die Menge $S$ der Spielsteine wird lexikographisch nummeriert und damit das ganze Spiel $D$ durch ein Wort $x$ über $\{0,1,\#\}^{*}$ auf das Eingabeband geschrieben.

Ein Beispiel wäre hilfreich: Nehmen wir z.B. das Spielbrett Nr. 1 von oben als Anfangsbelegung und basteln und daraus das gesamte Spiel $D_1$:

$\alpha(1,2) = (1,0,0,0)$, $\alpha(1,3) = (0,1,0,1)$ und $\alpha(2,3) = (1,1,1,0)$, alle anderen Felder sind leer

So haben das folgende Wort auf unserer $KTM$ (ich habe aus Faulheit nicht alle 16 Spielsteine auf das Band codiert, sondern nur den ersten $000$ und letzten $1111$, dazwischen mit Punkten $...$ gearbeitet):

$\gamma D(D_1) = 0\#0\#0\#0\#...\#1\#1\#1\#1\#\#\varepsilon\#1\#0\#0\#0\#0\#1\#0\#1\#\varepsilon\#\varepsilon\#1\#1\#1\#0\#\varepsilon\#\varepsilon\#\varepsilon$

Zunächst codieren wir also alle 16 Möglichkeiten der Steine, d.h. den Steinsatz auf das Band. Anschließend kommt die Anfangsbelegung $\alpha$ des Bretts, nachdem wir sie mit $\#\#$ von dem auf dem Band ebenfalls codierten Steinsatz getrennt haben. Nicht vergessen: mit $\varepsilon$ werden leere Felder bezeichnet.

Die Menge aller lösbaren Belegungen nennen wir:

$2D-DOMINO = \{x\in\{0,1,\#\}^{*}\mid x\in Bild(\gamma D)$ und ${\gamma D}^{-1}(x)$ ist lösbar $\}$.

Aufdröseln: $2D-DOMINO$ besteht also aus dem Wort $x$ über dem Alphabet $\{0,1,\#\}^{*}$, wobei $x$ ein Bild von $\gamma D$ und die Inverse von $\gamma D(x)$ lösbar sein muss. $\gamma D$ ist unsere Funktion, die als Parameter unser komplettes Spiel $D$ (Spielbrettgräße, Steine, Anfangsbelegung) als Wort bekommt und uns dazu das $x$ (das Spiel $D$ als codiertes Wort) ausgibt. Damit ist $D$ unser Definitionsbereich für die Funktion $\gamma D$ und $x$ liegt im Bildbereich von $\gamma D$. Wenn nun auch noch das Spiel $D$ lösbar ist (nicht jede Initialbelegung auf dem Spielbrett hat eine Lösung), so gehört das zum Spiel $D$ codierte Wort zur Menge $2D-DOMINO$. Anhand unseres Beispiels von Spielbrett Nr. 1 haben wir zusammengefasst:

$D_1 = (N,S,\alpha)$ (unser Spiel)

$S = \{\{0,0,0,0\}, \{0,0,0,1\}, ...,\{1,1,1,1\}\}$ (unsere Spielsteine)

$\alpha(1,2) = (1,0,0,0)$, $\alpha(1,3) = (0,1,0,1)$ und $\alpha(2,3) = (1,1,1,0)$ (unsere Anfangsbelegung)

$\gamma D(D_1) = 0\#0\#0\#0\#...\#1\#1\#1\#1\#\#\varepsilon\#1\#0\#0\#0\#0\#1\#0\#1\#\varepsilon\#\varepsilon\#1\#1\#1\#0\#\varepsilon\#\varepsilon\#\varepsilon$ (unser Spiel als codiertes Wort $x$)

$x\in Bild(\gamma D(D_1))$ (das Wort ist, wie man oben sehen kann im Bildbereich der Funktion $\gamma D$) und

$\gamma D^{-1}(x) = D_1)$ (die Inverse $\gamma D^{-1}$ gibt uns zu jedem $x$ ein $D$ zurück, d.h. zu jedem Codewort das zugehörige Spiel. Und das Spiel ist lösbar. Es gibt also eine vollständige Belegung $\beta$ für das Spiel $D_1$, die die oben genannten Regeln nicht verletzt).

Bitte beachtet, dass hier das ganze Spiel $D$ ohne zu testende Belegung auf das Band codiert wird. Die zu testende Belegung ist unsere Hilfseingabe $\beta$. Codieren wir also unser Spiel $D$ zusammen mit unserer zu testenden Hilfseingabe $\beta$ auf das Band, so können wir anhand der Regeln in quadratischer Zeit prüfen ob $\beta$ eine Lösung für $D$ ist.

Damit ist die Menge $2D-DOMINO\in NP$.

Bitte beachten: im Gegensatz zum vorherigen Beitrag zu KE3 haben wir hier zuerst die Zugehörigkeit von $2D-DOMINO$ zur $NP$ gezeigt indem wir eine $KTM$ angegeben haben, die mit unserem codierten Wort auf dem Eingabeband und unserer zu testenden Hilfseingabe diese Lösung überprüft. Nun müssen wir für die Vollständigkeit noch $2D-DOMINO$ ist $NP$-hart zeigen (ich Wiederhole mich häufig, was die Kriterien für die Vollständigkeit betrifft, aber besser zu viel als zu wenig).

Dazu zeigen wir, dass alle Mengen aus $M\in NP$ auf unsere Problemmenge $2D-DOMINO$ in polynomieller Zeit reduzieren lassen, formal ausgedrückt:

${M}\leq_{pol} 2D-DOMINO$

Denn das ist ja der Charme an der Vollständigkeit: können wir eine vollständige Menge reduzieren, können wir alle reduzieren (für eine Auffrischung, schaut in den letzten Beitrag zu KE3). Sobald das getan ist, gilt die Menge $2D-DOMINO$ als $NP$-vollständig.

Das Prinzip der in der KE4 beschriebenen Probleme ist es zu zeigen, dass man zunächst für alle Mengen $M\in NP$ diese auf $2D-DOMINO$ reduziert und dann $2D-DOMINO$ nutzt um es dann auf das Problem $SAT$, $SAT$ dann auf $3SAT$ usw. zu reduzieren und so die $NP$-Vollständigkeit der Probleme zu beweisen. D.h. haben wir eine Menge initial als $NP$-Vollständig nachgewiesen, so können wir durch einfache Reduzierung andere Mengen sofort auch als $NP$-Vollständig nachweisen (hier sei auf den Abschnitt zu Cook im Beitrag zu KE3 verwiesen).

Zeitbedingt muss ich den Beweis der $NP$-Härte für $2D-DOMINO$ überspringen, werde versuchen ihn für $SAT$ und $3SAT$ im nächsten Beitrag nachzuholen, da $SAT$ doch häufiger anzutreffen ist als $2D-DOMINO$. Wer eine schöne Beschreibung des Beweises aus dem Skript hat, immer her damit.

Antwort zum Lernziel: zunächst wird wie bei allen Beweisen der Vollständigkeit gezeigt, dass sich $2D-DOMINO$ in $NP$ befindet indem man ein Verfahren angibt, dass das Problem in nichtdeterministischer polynomieller Zeit löst, d.h. eine $KTM$, dass unsere Prüfbelegung (sog. Hilfseingabe) auf Korrektheit prüft. Anschließend zeigt man die $NP$-Härte von $2D-DOMINO$ mittels zwei Möglichkeiten:

1. die leichte: wir reduzieren $2D-DOMINO$ polynomiell auf ein bekanntes, $NP$-schweres Problem indem man ein Verfahren angibt, dass diese Reduktion in polynomieller Zeit schafft oder

2. die schwere: wenn wir kein Problem haben (Henne-Ei-Problem), müssen wir eines angeben, bei dem einzusehen ist, dass es definitiv in $NP$ liegt (ob es praxistauglich ist, ist egal). Man konstruiert sich sozusagen ein Problem. Auf dieses wird dann $2D-DOMINO$ reduziert.

Stephen A. Cook hat uns die Arbeit aber abgenommen und $SAT$ als $NP$-vollständig bewiesen, so dass wir die $NP$-Vollständigkeit von $2D-DOMINO$ beweisen könnten wenn wir es auf $SAT$ zurückführen.

Lernziel 2

Wie beweist man die $NP$-Vollständigkeit einer Menge?

Antwort zum Lernziel: Doppelt hält besser: Für die $NP$-Vollständigkeit eines Problems müssen wir also zuerst nachweisen, dass es in $NP$ liegt (dazu geben wir eine $KTM$ an, die das Problem in Polynomzeit mit einer gegebenen Hilfseingabe entscheiden kann. Oder eine $NTM$ zum vorherigen Ergebnis-orakeln, denn das orakeln ist das $N$ in $NTM$). Anschließend muss noch die $NP$-härte nachgewiesen werden, indem wir ein vollständiges Problem in Polynomzeit auf unseres reduzieren oder auf Reduktion verzichten und die $NP$-Härte direkt nachweisen.

Wenn wir also noch kein $NP$-vollständiges Problem haben, dass wir reduzieren können, haben wir ein klassisches Henne-Ei-Problem. Zum Glück gibt es kluge Leute, die das auch ohne die Reduzierung geschafft haben. Und sie leben auch noch: einer davon ist Stephen A. Cook mit seinem berühmten Satz von Cook. In diesem zeigte er die Vollständigkeit des $SAT$-Problems. Wir wollen den Beweis mal nachvollziehen, so als Kompensation zum fehlenden $2D-DOMINO$-Beweis von oben.

Im nächsten Beitrag geht es dann entsprechend um $SAT$.