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 = {anbn} 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...
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 = {anbncn} ist nicht kontextfrei.