Kontextfreie Grammatik
Einführung
Sprachen haben ihre eigenen Regeln, wie Sätze strukturiert und Worte gebildet werden dürfen. Einige dieser Sprachen können recht einfach sein, während andere komplexer und vielschichtiger sind. In der Welt der Informatik und Mathematik haben wir auch "Sprachen", aber statt mit Wörtern und Sätzen arbeiten wir mit Zeichen und Zeichenketten. Eine solche Kategorie dieser Sprachen wird "kontextfreie Sprachen" genannt.
Kontextfreie Sprachen sind eine Art von formalen Sprachen. Eine Sprache ist vereinfacht eine Menge von Zeichenketten (Worte), die aus einem bestimmten Alphabet generiert werden und bestimmten Regeln folgen.
"Kontextfrei" bedeutet, dass die Zeichen oder Worte in der Sprache in einem bestimmten Kontext unabhängig voneinander interpretiert werden können. Das heißt, ihre Bedeutung oder Interpretation hängt nicht von anderen Zeichen oder Wörtern im Satz ab.
Der Begriff "kontextfrei" kann ein wenig irreführend sein, da er nicht unbedingt bedeutet, dass es keinen Kontext gibt. Stattdessen bedeutet es, dass die Regeln, die die Form der Sprache bestimmen, ohne Kontext angewendet werden können.
Hierzu ein Beispiel:
Wir bertachten eine Sprache von korrekt verschachtelten runden Klammern. Jede öffnende Klammer ( soll ein korrespondierendes Gegenstück ) besitzen. Jedes Paare ist korrekt verschachtelt wenn sie sich nicht überkreuzen.
Gültige Klammersetzung
()
(())
()()
((()))
Ungültige Klammersetzung
)( - Hier sind die Klammern in der falschen Reihenfolge.
(() - Es fehlt eine schließende Klammer.
()) - Es gibt eine zusätzliche schließende Klammer ohne ein korrespondierendes öffnendes Gegenstück.
((()) - Es fehlt erneut eine schließende Klammer.
Im Klammern-Beispiel hängt die Erzeugung oder Interpretation einer Klammer nicht davon ab, was vor oder nach ihr steht. Das macht die Grammatik kontextfrei. Es geht nur darum, ob die Klammern korrekt verschachtelt sind oder nicht, und nicht darum, in welchem spezifischen Kontext sie sich befinden. Das ist der Grund, warum wir sagen, dass das Beispiel ohne Kontext ist.
Eine kontextfreie Grammatik ist eine Grammatik, in der alle Produktionsregeln kontextfrei sind. Eine Produktionsregel ist kontextfrei, wenn die linke Seite der Regel ein Nichtterminalsymbol ist und die rechte Seite der Regel ein beliebiges Wort aus Terminal- und Nichtterminalsymbolen ist. Zusammenfassend gilt:
Die linke Seite der Produktionsregeln besteht nur aus Nichtterminalsymbolen.
Die rechte Seite jeder Produktionsregel ist ein beliebiges Wort aus Terminal- und Nichtterminalsymbolen.
Es gibt ein Startsymbol.
Die kontextfreie Grammatik für das Beispiel lautet also:
L= {( n ,) n | 1<=n}
A -> (A) | ()
Ein Sprache ist kontextfrei, wenn sie durch eine kontextfreie Grammatik beschrieben und von einem Kellerautoam
Eine Sprache ist nicht kontextfrei, wenn sie nicht durch eine kontextfreie Grammatik beschrieben werden kann.
Abgrenzung zur regulärer Grammatik
Kontextfreie Grammatiken und reguläre Grammatiken sind zwei unterschiedliche Typen von Grammatiken. Dennoch gibt es eine inklusive Beziehung zwischen ihnen.
Hier eine kurze Übersicht:
Reguläre Grammatiken:
Produzieren reguläre Sprachen.
Können von endlichen Automaten erkannt werden.
Kontextfreie Grammatiken:
Produzieren kontextfreie Sprachen.
Können von Kellerautomaten (Pushdown Automata, PDA) erkannt werden.
Jede reguläre Sprache ist auch eine kontextfreie Sprache, das heißt, reguläre Grammatiken sind ein Spezialfall von kontextfreien Grammatiken. Das bedeutet, dass alles, was von einem endlichen Automaten erkannt werden kann, auch von einem Kellerautomaten erkannt werden kann, jedoch nicht umgekehrt.
Automaten
Kontextfreie Sprachen können effektiv durch Kellerautomaten (auch Pushdown-Automaten genannt) beschrieben werden, da diese eine besondere Fähigkeit besitzen, die einfache endliche Automaten nicht haben: einen Stapelspeicher (Stack oder "Keller"). Dieser Stapelspeicher ermöglicht es dem Kellerautomaten, eine Form von Gedächtnis oder Hierarchie in der Verarbeitung von Eingabezeichenketten zu haben, was für viele kontextfreie Sprachen notwendig ist.
Ein Kellerautomat für korrekt verschachtelte Klammern könnte folgendermaßen aussehen:
Q: Zustände Q={ q0,q1,qaccept,qreject}
Σ: Eingabealphabet Σ={(,)}
Γ: Kellersymbole
Γ={Z,(}
Z ist das Kellerboden-Symbol.
( wird auf den Stack gelegt, wenn eine öffnende Klammer gelesen wird.
q0: Startzustand
Der Automat beginnt im Zustand q0
Z: Startsymbol des Stacks
Der Stack beginnt mit dem Symbol Z zu Beginn der Verarbeitung.
δ: Übergangsfunktionen (einige davon sind hier aufgeführt):
Bei Erhalt von ( in Zustand q0 mit Z auf dem Stack: in den Zustand qo wechseln, ( auf den Stack legen.
Bei Erhalt von ( in Zustand q0 mit ( auf dem Stack: in den Zustand q0 wechseln, ein weiteres ( auf den Stack legen.
Bei Erhalt von ) in Zustand q0 mit ( auf dem Stack: in den Zustand q0 wechseln und ( vom Stack entfernen.
Bei Erhalt von ) in Zustand q0 mit Z auf dem Stack: in den Zustand qreject wechseln (dies bedeutet, dass mehr schließende als öffnende Klammern vorhanden sind).
Wenn die Eingabe in Zustand q0 endet und Z auf dem Stack ist: in den Zustand qaccept wechseln.
Wenn die Eingabe in Zustand q0 endet, aber ( auf dem Stack ist: in den Zustand qreject wechseln (dies bedeutet, dass nicht alle öffnenden Klammern geschlossen wurden).
Dieser Kellerautomat kann korrekt verschachtelte Klammern erkennen und ist ein typisches Beispiel für die Mächtigkeit von Kellerautomaten bei der Verarbeitung von kontextfreien Sprachen.
Es ist jedoch wichtig zu beachten, dass nicht alle kontextfreien Sprachen leicht durch einen Kellerautomaten beschrieben werden können, und manchmal kann das Design solcher Automaten kompliziert sein. Dennoch hat der Kellerautomat genau die richtige Mächtigkeit, um alle kontextfreien Sprachen zu erkennen und keine darüber hinaus. Das bedeutet, es gibt einige Sprachen, die ein Kellerautomat nicht erkennen kann.
Kontextfrei Grammatik als BNF
BNF ist eine kontextfreie Grammatik. Die Produktionsregeln von BNF erfüllen alle Kriterien für kontextfreie Produktionsregeln:
Die linke Seite der Regel ist ein Nichtterminalsymbol.
Die rechte Seite der Regel ist ein beliebiges Wort aus Terminal- und Nichtterminalsymbolen.
Kontextfreie Grammatiken lassen sich also in der Backus Naur Form (kurz BNF) definieren. Eine BNF zum obigen Beispiel wäre:
<Klammern> ::= ε | ( <Klammern> ) | <Klammern> <Klammern>
Die BNF lässt sich wie folgt interpretieren.
<Klammern> ist das Startsymbol der Grammatik und entspricht einem nicht Terminal.
Eine korrekt verschachtelte Klammersprache kann leer sein (d.h. ε oder leeres Wort und hier ein Terminal), was den Fall einer leeren Zeichenkette abdeckt.
Oder es kann mit einer öffnenden Klammer (Terminal) beginnen, gefolgt von einer weiteren korrekt verschachtelten Klammersprache und dann einer schließenden Klammer (Terminal).
Schließlich kann es auch zwei korrekt verschachtelte Klammersprachen hintereinander geben, z. B. () gefolgt von () ergibt ()().
Diese BNF beschreibt eine kontextfreie Grammatik, da sie auf rekursive Definitionen zurückgreift, um korrekt verschachtelte Strukturen zu erzeugen.
Der String ()() lässt sich mithilfe der zuvor definierten BNF für verschachtelte Klammern Schritt für Schritt wie folgt auflösen:
Der String ()() entspricht der Regel <Klammern> <Klammern>, da er aus zwei Teilen besteht, die jeweils () entsprechen.
Also: ()() -> <Klammern><Klammern>Wenn wir den ersten Teil () betrachten, passt er zur Regel ( <Klammern> ), wobei <Klammern> hier ε repräsentiert (weil zwischen den Klammern nichts steht).
Daher: () -> ( ε )Der zweite Teil des Strings () wird auf die gleiche Weise analysiert, da er identisch mit dem ersten ist.
Wieder: () -> ( ε )
Zusammengesetzt ergibt sich:
()() -> ( ε ) ( ε )