Kontextfreie Grammatik

Aus SibiWiki
Version vom 5. November 2023, 10:39 Uhr von Akaibel (Diskussion | Beiträge) (→‎Zusammenhang zum Kellerautomat)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen

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.