Kontextfreie Grammatik
aus Wikipedia, der freien Enzyklopädie
Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ-2-Grammatiken der Chomsky-Hierarchie.
[Bearbeiten] Definition
Eine kontextfreie Grammatik G ist eine kontextsensitive Grammatik, deren Produktionsregeln soweit eingeschränkt sind, dass immer genau ein Nichtterminal durch eine evtl. auch leere Folge von Zeichen (Nichtterminale oder Terminale) ersetzt wird. Mathematisch wird dies durch 
beschrieben.
Man schreibt 
.
Typ-2-Grammatiken besitzen nur Regeln der Form 
, wobei A ein Nichtterminal und γ ein Wort bestehend aus Terminalen und Nichtterminalen ist. (Um das leere Wort 
zu erzeugen, darf hier für γ auch verwendet werden.)
Eine Erweiterung der kontextfreien Grammatiken bilden die stochastischen kontextfreien Grammatiken. Hier wird jeder Produktionsregel eine Auftretenswahrscheinlichkeit zugeordnet: 
mit 
[Bearbeiten] 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 (NKA, auch NPDA für englisch Nondeterministic push down automat) erkannt werden können. Eine Teilmenge dieser Sprachen bilden die theoretische Basis für die Syntax der meisten Programmiersprachen.
Siehe auch:
