Kontextfreie Grammatik

Definition

Eine Grammatik G wird durch ein 4-Tupel (N, T, S, P) definiert:

• N ist die Menge der Nichtterminalsymbole.
• T ist die Menge der Terminalsymbole.
• S ∈ N ist das Startsymbol.
• P ist die Menge der Produktionsregeln.

Eine kontextfreie Grammatik ist eine Grammatik, bei der alle Produktionen den folgenden Anforderungen genügen:

• links darf nur ein Nichtterminal stehen.
• rechts darf eine (endliche) Kombination von Terminal- und Nichtterminal-Symbolen stehen.

Somit ist klar, dass jede reguläre Grammatik auch eine kontextfreie Grammatik ist.

Beispiel

Die Sprache L = {aⁿbⁿ} lässt sich mit einer kontextfreien Grammatik erzeugen:

• G= (N, T, S, P)
• Nichtterminalsymbole N = {S}
• Terminalsymbole T = {a,b}
• Startsymbol S = S
• Produktionsregeln P = {
  • S → aSb | ε
• }

Beispiel für die Ableitung eines Wortes

Dass das Wort "aabb" zur Sprache L gehört, lässt sich durch folgende Ableitung zeigen:

• S → aSb → aaSbb → aabb

Bei der letzten Ableitung wurde das S durch nichts (ε) ersetzt.

Zusammenhang zum Kellerautomat

Jede kontextfreie Sprache lässt sich durch einen nicht-deterministischen Kellerautomat überprüfen.

Grenzen der kontextfreien Sprache

Die Sprache L = {aⁿbⁿcⁿ} ist nicht kontextfrei.