Fachkonzept - Kontextfreie Sprache
Grammatiken im Vergleich
Grammatiken können unterschiedlich komplex sein.
Die folgende Grammatik zur Beschreibung von Binärzahlen hat eine einfache Strukur.
S -> 0B B -> λ S -> 1A A -> 0A A -> 1A A -> λ
Alle Produktionen sind vom Typ X -> aY oder X -> λ, wobei X, Y für
Nichtterminalsymbole stehen und a für ein Terminalsymbol. Grammatiken dieses Typs werden auch reguläre
Grammatiken genannt.
Zur Beschreibung der Sprache der vereinfachten Rechenausdrücke kann man die folgende Grammatik benutzen:
A -> A+S A -> S S -> S*F S -> F F -> (A) F -> z
Die Produktionen sind hier vom Typ X -> w, wobei X für ein
Nichtterminalsymbol steht und w für ein beliebiges Wort aus Terminal- und Nichtterminalsymbolen.
Noch allgemeinere Produktionen haben wir zur Beschreibung der Sprache der vereinfachten XML-artigen Ausdrücke benutzt:
S -> <aAT> S -> <bBT> T -> aAT T -> bBT T -> M Aa -> aA Ab -> bA AM -> Ma Ba -> aB Bb -> bB BM -> Mb M -> >N N -> aN N -> bN N -> cN N -> </
Hier besteht bei einigen Produktionen die linke Seite nicht nur aus einem einzigen Nichtterminalsymbol, sondern einem Nichtterminalsymbolen umgeben von weiteren Symbolen.
Je nach Komplexität der Produktionen ergeben sich unterschiedliche Anforderungen an die Automaten,
die zur Spracherkennung konstruiert werden sollen.
Wir werden uns im Folgenden auf Produktionen vom Typ X -> w konzentrieren.
Kontextfreie Sprachen
Eine Produktion u -> v heißt kontextfrei genau dann, wenn gilt:
Die linke Seite u der Produktion ist ein Nichtterminalsymbol.
Die rechte Seite v der Produktion ist ein beliebiges Wort bestehend aus
Terminal- und Nichtterminalsymbolen. Hierzu zählt auch das leere Wort.
Eine Grammatik heißt kontextfrei genau dann, wenn alle Produktionen der Grammatik kontextfrei sind.
Eine Sprache heißt kontextfrei genau dann, wenn es eine kontextfreie Grammatik gibt, die diese Sprache erzeugt.
Beispiel - die Sprache LRA:
A -> A+S A -> S S -> S*F S -> F F -> (A) F -> z
Die Grammatik zur Sprache LRA ist kontextfrei. Die Sprache LRA ist infolgedessen ebenfalls kontextfrei.
Beispiel - die Sprache LMyXML:
S ->S -> T -> aAT T -> bBT T -> M Aa -> aA Ab -> bA AM -> Ma Ba -> aB Bb -> bB BM -> Mb M -> >N M -> aM M -> bM M -> cM M -> Die Grammatik zur Sprache LMyXML ist nicht kontextfrei, da es Produktionen gibt, bei denen auf der linken Seite nicht nur ein Nichtterminalsymbol steht. Hieraus kann man aber noch nicht erschließen, dass die Sprache LMyXML nicht kontextfrei ist. Es könnte weitere - auch kontextfreie - Grammatiken für diese Sprache geben. Im vorliegenden Fall kann man beweisen, dass es keine kontextfreien Grammatiken für die Sprache LMyXML gibt. Die Sprache LMyXML ist also tatsächlich nicht kontextfrei.