Zusammenfassung

Grammatiken sind Mechanismen zur Generierung von Sprachen. Eine Sprache ist eine Mengen von Wörtern. Diese Menge muss nicht endlich sein, sondern kann abzählbar unendlich sein.

Grammatiken dienen dazu, Sprachen zu beschreiben. Sie bieten also eine endliche Darstellung von potentiell unendlichen Wortmengen.

Grammatiken werden nach Chomsky klassifiziert. Die einfachste Form sind die regulären Grammatiken, sie haben genau die Beschreibungsstärke von endlichen Automaten.

Die wichtigste Klasse von Grammatiken sind die kontextfreien Grammatiken. Nichtterminalsymbole werden hier unabhängig von ihrer Umgebung ersetzt. Programmiersprachen können mithilfe von kontextfreien Grammatiken beschrieben werden. Sie sind damit ein wichtiges Werkzeug für den Compilerbau.

Die Klasse der regulären Sprachen ist eine echte Teilmenge der Menge der kontextfreien Sprachen.