Theoretische Informatik

Definition:  Sei G = (V, T, P, S) eine Grammatik, wobei V die Menge der Variablen ist, T die Menge der Terminal­zeichen, P die Menge der Produktionen und S das Startsymbol, ferner A = V ∪ T das Gesamt­alphabet.

Die Grammatik G heißt kontext­sensitiv, wenn jede Produktion von der Form

uXvuyv

mit X ∈ V,  y ∈ A⁺ und u, v ∈ A* ist.

Als Ausnahme ist die Produktion S → ε erlaubt, wobei dann S nicht auf der rechten Seite einer Produktion vorkommen darf.

Eine Sprache heißt kontext­sensitiv, wenn es eine kontext­sensitive Grammatik gibt, die sie erzeugt.

Definition:  Eine kontext­sensitive Grammatik ist in Kuroda-Normalform, wenn jede Produktion von der Form

X		a	,
X		Y	,
X		YZ	oder
WX		YZ

mit a ∈ T und W, X, Y, Z ∈ V ist.

Als Ausnahme ist die Produktion Sε erlaubt, um das leere Wort ε zu erzeugen; dann darf S aber nicht auf der rechten Seite einer Produktion vorkommen.

Satz:  Zu jeder kontext­sensitiven Sprache gibt es eine kontext­sensitive Grammatik in Kuroda-Normalform.

Definition:  Eine Grammatik heißt monoton oder expansiv, wenn für alle Produktionen uv gilt

|u| ≤ |v|

Bei einer Ersetzung von u durch v in einem Wort w wird also w niemals kürzer.

Als Ausnahme ist die Produktion Sε erlaubt; dann darf S aber nicht auf der rechten Seite einer Produktion vorkommen.

Satz:  Zu jeder kontext­sensitiven Sprache gibt es eine monotone Grammatik.