Formale Grammatik

Mathematische Modelle von Grammatiken - sogenannte formale Grammatiken - dienen der eindeutigen Erzeugung bzw. Beschreibung formaler Sprachen.

Eine formale Grammatik G besitzt eine Startvariable S sowie eine Menge P von Produktionsregeln, wobei durch Anwendung besagter Regeln neue Wörter aus der Startvariable erzeugt werden können. Eine Ableitung ist dann vollständig, alle nicht-terminalen Symbole (Variablen) durch Ableitungen verschwunden bzw. durch terminal-Symbole (Zeichen) ersetzt worden sind. Das erzeugte Wort gehört dann zu der von der Grammatik erzeugten Sprache L(G).

Anwendung finden formale Grammatiken in der theoretischen Informatik - beispielsweise im Compilerbau - um festzustellen, ob ein Wort Element einer bestimmten Sprache ist.