Kontextfreie Grammatik

nur relevant für den Leistungskurs!

Fachbegriffe

Nicht-terminal-symbole, Terminal-Symbole, Startsymbol, Produktionsregeln, Ableitung (eines Wortes), Sprache

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 von einer kontextfreien Grammatik erzeugte Sprache lässt sich durch einen nicht-deterministischen Kellerautomat überprüfen.
• Zu jeder von einem nicht-deterministischen Kellerautomat erkannten Sprache gibt es eine kontextfreie Grammatik.

Die Frage nach dem "Warum?" geht auch über den Informatik-LK hinaus und bleibt hier unbeantwortet.
Irgendetwas muss ja auch für das Studium noch übrig bleiben...

• • Wer sich den (langatmigen!!) Beweis mal anschauen will:
    Theorie der Informatik, Kontextfreie Sprachen II, Universität Basel 2014
    S. 17 ff.

Zu beachten ist:

Der nicht-deterministische Kellerautomat ist mächtiger als der deterministische Kellerautomat!
D.h. es gibt Sprachen, die von einem Nicht-Deterministischen Kellerautomaten geprüft werden können, nicht aber von einem Deterministischen Kellerautomaten.

Vgl. Kellerautomat

Grenzen der kontextfreien Sprache

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