Kontextfreie Grammatik

Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ-2-Grammatiken der Chomsky-Hierarchie.

Definition

Eine kontextfreie Grammatik $G$ ist eine kontextsensitive Grammatik, deren Produktionsregeln soweit eingeschränkt sind, dass immer genau ein Nichtterminal durch eine nichtleere Folge von Zeichen (Nichtterminale oder Terminale) ersetzt wird. Mathematisch wird dies durch $\forall (w_{1}\rightarrow w_{2})\in P:(w_{1}\in N)\land \left(w_{2}\in (N\cup T)^{\star }\right)$ beschrieben.

Man schreibt $G\in {\mbox{Typ}}_{2}$.

Typ-2-Grammatiken besitzen nur Regeln der Form $A\rightarrow \gamma$, wobei $A$ ein Nichtterminal und $\gamma$ ein Wort bestehend aus Terminalen und Nichtterminalen ist. (Um das leere Wort $\varepsilon$ zu erzeugen, darf hier für $\gamma$ auch $\varepsilon$ verwendet werden.)

Von $G$ erzeugte Sprache

Die kontextfreien Grammatiken erzeugen genau die kontextfreien Sprachen, d. h. jede Typ-2-Grammatik erzeugt eine kontextfreie Sprache und zu jeder kontextfreien Sprache existiert eine Typ-2-Grammatik, die diese erzeugt.

Die kontextfreien Sprachen sind genau die Sprachen, die von einem nichtdeterministischen Kellerautomaten (NPDA) erkannt werden können. Eine Teilmenge dieser Sprachen bilden die theoretische Basis für die Syntax der meisten Programmiersprachen.

Siehe auch: Backus-Naur-Form