Kontextsensitive Grammatik

aus Wikipedia, der freien Enzyklopädie

Die kontextsensitiven Grammatiken sind eine Klasse formaler Grammatiken und identisch mit den Typ-1-Grammatiken der Chomsky-Hierarchie.

[Bearbeiten] Definition

Eine formale Grammatik G ist kontextsensitiv (Typ-1), wenn für jede Produktionsregel gilt: . Weniger formal bedeutet das: alle rechten Regelseiten sind nicht kürzer als die zugehörigen linken Regelseiten.

Man schreibt .

Im Gegensatz zu kontextfreien Grammatiken kann die Anzahl der Symbole auf der linken Regelseite auch größer als 1 sein.

Typ-1-Grammatiken besitzen Regeln der Form , wobei A ein Nichtterminal und α,β,x Wörter bestehend aus Terminalen (Σ) und Nichtterminalen (N) sind. Die Wörter α und β können leer sein, aber x muss mindestens ein Symbol (also ein Terminal oder ein Nichtterminal) enthalten.

An diesem Beispiel kann auch die Bezeichnung kontextsensitiv erklärt werden. Durch Regeln der Form ist es möglich, die Variable A durch x zu ersetzen aber nur dann, wenn A in einem bestimmten Kontext also hier zwischen α und β steht.

Einzige Ausnahme zu obiger Form bildet die Regel , die eventuell benötigt wird, das leere Wort abzuleiten. Sie darf aber nur dann verwendet werden, wenn das Startsymbol S auf keiner rechten Regelseite vorkommt.

Ableitungen werden niemals kürzer. Darum ist auch (Wortproblem), mit L kontextsensitive Sprache, entscheidbar.

[Bearbeiten] Von G erzeugte Sprache

Mit Hilfe kontextsensitiver Grammatiken lassen sich genau die kontextsensitiven Sprachen erzeugen. D.h. jede Typ-1-Grammatik erzeugt eine kontextsensitive Sprache und zu jeder kontextsensitiven Sprache existiert eine Typ-1-Grammatik, die diese erzeugt.

Die kontextsensitiven Sprachen sind genau die Sprachen, die von einer nichtdeterministischen, linear beschränkten Turingmaschine erkannt werden können; d.h. von einer nichtdeterministischen Turing-Maschine, deren Band linear durch die Länge der Eingabe beschränkt ist (d.h. es gibt eine konstante Zahl a so dass das Band der Turing-Maschine höchstens Felder besitzt, wobei x die Länge des Eingabewortes ist).