Kontextsensitive Sprachen

Grammatiken heißen kontextfrei, wenn alle Regeln so gestaltet sind, dass sie nicht von der Umgebung, in der sie angewendet werden können, abhängen. Jetzt wollen wir erlauben, dass die Regeln von der Umgebung abhängen. Wir nehmen dazu einfach die Umgebung in die Regeln auf.

Definition: Kontextsensitive Grammatik
Eine Grammatik heißt kontextsensitiv oder umgebungsabhängig, wenn alle Regeln von der Form {(w_{1}Aw_{2} \rightarrow w_{1}ww_{2})} mit A \in N sowie w \in T^{+} = T^{*} \backslash \{\epsilon\} und w_{1}, w_{2} \in T^{*} sind.

Wir stellen uns dazu vor, dass wir kontextfreie Regeln (A \rightarrow w) haben, die aber nur angewendet werden dürfen, wenn vor dem A ein w1 und dahinter ein w2 steht.

Eine Sprache heißt kontextsensitiv, wenn sie von einer kontextsensitiven Grammatik erzeugt wird. Offensichtlich ist jede kontextfreie Sprache auch kontextsensitiv.

Die Menge L = \{a^{n}b^{n}c^{n} \mid n \in \mathbb{N} ist kontextsensitiv. Zum Beweis geben wir eine kontextsensitive Grammatik an, denn die im Beitrag Allgemeine Regelsprachen (Beispiel 3) für diese Sprache angegebene Grammatik ist nicht kontextsensitiv. Die Regel (UT -> TU) ist nämlich keine kontextsensitive Regel.

Sei G = (VN, VT, P, S) gegeben mit
VN = {S, T, U, V, W}
VT = {a, b, c}
P = {(S -> aSTU | aTU),
     (aT -> ab),
     (bT -> bb),
     (bU -> bc),
     (cU -> cc),
     (UT -> UW),
     (UW -> VW),
     (VW -> VU),
     (VU -> TU)}
S = S

Die letzten vier Regeln kann man durch eine, allerdings nicht kontextsensitive Regel, nämlich die oben angesprochene {(UT \rightarrow TU)}, ersetzen.

Eine Anwendungssituation, bei der drei Folgen aus verschiedenen Zeichen jeweils gleich lang sind, tritt bei folgendem Problem auf: Manche Drucker stellen ein unterstrichenes Wort der Länge n dadurch dar, dass zuerst das Wort gedruckt wird, dann der Druckkopf n Schritte zurückgeht und dann n mal ein Buchstabe unterstrichen wird. Entsprechend muss ein solches Wort in einem fortlaufenden Text dargestellt werden. Eine solche Darstellung auf dem Bildschirm wäre sehr unvorteilhaft. Im Textverarbeitungsprogramm muss deshalb ein Unterprogramm integriert sein, das solche Zeichenketten erkennt.

In Pascal sind damit auch Prozeduren, Funktionen und Programme nicht kontextfrei, weil in den Ausdrücken Typüberprüfungen und Wertebereichsprüfungen (lokal) stattfinden müssen. Auch muss jede Variable vereinbart sein. Diese Objekte sind damit nicht unabhängig von ihrer Umgebung, genauer von den entsprechenden Vereinbarungsteilen. Dass die Analyse von Pascalprogrammen trotzdem relativ rasch möglich ist, beruht darauf, dass fast die ganze Analyse in Form einer LR(1) Analyse ablaufen kann. Man legt nur die Variablen in Tabellen ab und vergleicht die Typen mit den Werten dieser Tabellen.

An zwei Beispielen soll dies noch etwas erläutert werden:

  1. Die Sprache L = \{wcw \mid w \in \{a, b\}^{*}, c \in T^{*} \} ist kontextsensitiv. Diese Sprache könnte als Kurzform dafür aufgefasst werden, dass ein Bezeichner im voraus vereinbart sein muss. Das erste Auftreten von w wird als Vereinbarung interpretiert, dann kommt eine beliebige Zeichenfolge c, dann kommt der Aufruf von w.
  2. Die Sprache L = \{a^{n}b^{m}c^{n}d^{m} \mid n, m \in \mathbb{N} \} ist kontextsensitiv. Diese Sprache könnte als Kurzform für das Arbeiten mit Prozeduren mit Parametern aufgefasst werden. Mit an und bm werden die Parameterlisten zweier Prozeduren bei der Deklaration beschrieben, genauer die Anzahlen n und m ihrer formalen Parameter. Mit cn und dm werden die Aufrufe dieser Prozeduren beschrieben, genauer die Anzahlen der aktuellen Parameter. Durch die gleichen Exponenten n bzw. m wird also beschrieben, dass die Anzahl der aktuellen mit der Anzahl der formalen Parameter übereinstimmen muss.

Tiefer wollen wir in die Theorie der kontextsensitiven Sprachen nicht eindringen.

Aufgabe

Geben Sie eine kontextsensitive Grammatik zu der Sprache L = \{a^{n}b^{m}c^{n}d^{m} \mid n, m \in \mathbb{N} \} an.

Schlagwörter: