Das Thema Grammatiken soll zunächst im Skript nicht behandelt werden, damit ein gutes Kapitel zu den schwierigen Turing-Maschinen und der Komplexitätstheorie entstehen kann. Für die nicht ganz so komplizierten Grammatiken sei auf die Folien und bei Bedarf auf das Buch von Hopcroft, Ullman und Motwani verwiesen.

Eine kurze Übersicht über den behandelten Stoff wollen wir an dieser Stelle aber geben. Wenn einem das alles etwas sagt und man damit arbeiten kann, dann kennt man sich in diesem Teil gut aus.

Wir haben zunächst die Grammatik eingeführt. Dort waren dann noch die Begriffe Nonterminal, Terminal, Produktion und Startsymbol wichtig. Diese beschreiben quasi was eine Grammatik ist. Um auch zu beschreiben, was man mit einer Grammatik machen kann, waren dann die Begriffe Ableitung und (Generierte) Sprache wichtig und nebenher noch der Begriff der Äquivalenz.

Dann haben wir die Grammatiken eingeschränkt und haben die kontextfreie Grammatik (oder auch Typ-2-Grammatik) und die rechtslineare Grammatik (auch Typ-3-Grammatik) eingeführt. Bei kontextfreien Grammatiken traten dann noch die Begriffe \(\lambda\)-Produktion und \(\lambda\)-frei auf.

Für die kontextfreien Grammatiken haben wir die Sprachfamilie CF (context free) eingeführt.

Wir haben dann zwei Konstruktionstechniken für Grammatiken kennengelernt, Abschlusseigenschaften der Sprachfamilie CF betrachtet und gesehen, dass rechtslineare Grammatiken und DFAs äquivalent sind sowie erwähnt, dass kontextfreie Grammatiken und Kellerautomaten äquivalent sind.

Dann haben wir die Chomsky-Normalform kennengelernt und ein Verfahren betrachtet, wie man diese herstellen kann. Im ersten Schritt dieses Verfahrens war zudem ein Test enthalten, mit dem man testen kann, ob \(\lambda \in L(G)\) gilt und im dritten Schritt war ein Verfahren enthalten, mit dem man eine Grammatik reduzieren kann.

Zum Schluss haben wir dann noch das Pumping Lemma für kontextfreie Sprachen kennengelernt und damit gezeigt, dass es Sprachen gibt, die nicht kontextfrei sind.