close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

11 Wie verhalten sich kontextfreie Sprachen zueinan- der?

EinbettenHerunterladen
11 Wie verhalten sich kontextfreie Sprachen zueinander?
Bei diesem Kapitel kann man den Eindruck eines Déjà-vu-Erlebnisses haben.
Nehmen wir an, es wird uns eine Sprache M f G vorgegeben, die über ein Mengenprädikat P
definiert wird, also M = {x | P(x)}. Gesucht ist eine Grammatik für M. Wenn wir zu M eine
reguläre Grammatik gefunden haben, ist das Problem gelöst. Finden wir keine oder wenden wir
gleich das Pumping-Lemma für reguläre Sprachen an und stellen fest, dass diese notwendige
Bedingung nicht erfüllt ist, muss man es mit einer kontextfreien Grammatik versuchen.
Gibt es ein Kriterium, mit dem wir entscheiden können, ob überhaupt Chancen bestehen, eine
solche zu finden, oder ob es grundsätzlich keine kontextfreie Grammatik für die vorgelegte
Sprache gibt? Wir suchen also nach notwendigen Eigenschaften, die alle kontextfreien Sprachen
haben müssen. Hat eine Sprache nicht diese Eigenschaft, kann sie nicht kontextfrei sein.
Ein Ansatz zum Finden eines solchen Kriteriums ist die Einsicht, dass, wenn Wörter lange
genug11 sind, bei der Ableitung des Wortes mindestens ein Nichtterminal rekursiv auftritt.
Satz von Bar-Hillel/Perles/Shamir (Pumping-Lemma für kontextfreie Sprachen):
Sei L eine kontextfreie Sprache. Dann gibt es ein n 0 ù so, dass alle Wörter ω mit |ω| $ n in
5 Teile zerlegt werden können, also ω = uvwxy, mit |vx| $1 und |vwx| # n, und alle Wörter
uviwxiy mit i $ 0 sind auch Wörter der Sprache.
Beweis(idee):
Wenn n genügend groß ist, muss bei der Ableitung von ω mindestens ein Nichtterminal wiederholt auftreten, also z.B. S Y* uAy Y* uvAxy Y* uvwxy. Statt die „A Y* w”-Alternative
gleich zu nehmen, kann man die „A Y* vAx”-Alternative iterieren. Also gilt auch S Y* uAy Y*
uvAxy Y* uvvAxxy Y* uviwxiy.
Anschaulich kann man den Sachverhalt folgendermaßen darstellen:
11
"Lange genug" bedeute z.B. größer 2|Anzahl der Produktionen| (oder größer |Anzahl der
Produktionen|C|maximal lange rechte Seite|). Dann ist garantiert, dass ein Nichtterminal rekursiv auftreten muss.
89
Ê
Zum besseren Verständnis betrachte man als Beispiel die Sprache L = {anbncn | n $ 1}. Wie
man es auch immer in 5 Teile zerlegt, die u.a. Varianten sind nicht auf die Form mit gleichvielen
a, b und c zu bringen.
Genauer muss man so argumentieren: Angenommen die Sprache L wäre kontextfrei. Dann
gibt es ein n so, dass für alle Wörter z 0 L mit |z| $ n die drei Bedingungen des PumpingLemmas erfüllt sind. Wir wählen also ein beliebiges (aber dann festes) n und dazu das Wort z
= anbncn. Dann kann z zerlegt werden in z = uvwxy und es gelten die zwei Bedingungen |vwx|
# n sowie |vx| $1. Dann ist vwx aber entweder ein Teilwort von anbn oder von bncn. Damit kann
es nicht möglich sein, dass uviwxiy schon für i = 2 die gleiche Anzahl von a, b und c hat. Das ist
ein Widerspruch zur dritten Bedingung des Pumping-Lemmas, die sogar für alle i $0 gelten
muss, und damit zur Annahme „L ist kontextfrei”.
Ê
Die Pumping-Lemma-Eigenschaft ist auch im kontextfreien Fall nicht hinreichend. Es gibt
Sprachen mit diesen Eigenschaften, die aber nicht kontextfrei sind.
90
Um die Frage beantworten zu können, ob eine vorgelegte Sprache kontextfrei ist, kann man
ggf. folgende Beziehungen verwenden:
Behauptung:
Sei Σ ein Alphabet und L, L1, L2 f Σ* seien kontextfreie Sprachen. Dann sind die folgenden
Sprachen auch kontextfrei: L1 c L2 (Vereinigung), L1 B L2 (Konkatenation), L* (Kleene-Abschluss), LR (Spiegelsprache).
Beweis:
91
Behauptung:
Die kontextfreien Sprachen sind nicht abgeschlossen unter Komplement Σ* \ L und Durchschnitt L1 1 L2 .
Beweis:
92
12 Wie kann man kontextfreie Sprachen noch charakterisieren (Kellerautomaten)?
In diesem Kapitel verfolgen wir einen ähnlichen Ansatz wie bei der Einführung von endlichen
Automaten. Was der endliche Automat für reguläre, ist der Kellerautomat für kontextfreie
Grammatiken. Also: Was man mit einer kontextfreien Grammatik produzieren kann, lässt sich
mit einem geeigneten Kellerautomaten analysieren.
Zur Motivation versuchen wir wieder, eine Grammatik graphisch darzustellen, wie wir es
getan haben, um die Äquivalenz zwischen regulären Grammatiken und endlichen Automaten zu
demonstrieren, hier also am Beispiel von S 6 aSB | g, B 6 b
Man könnte diese Darstellung als einen hierarchischen nichtdeterministischen endlichen
Automaten nennen, der beschreibt, in welcher Reihenfolge die Produktionen bei der Analyse
angewendet werden können. Nur geht es nicht so glatt wie bei gewöhnlichen endlichen Automaten. Beim Verlassen des Knotens bei S bleibt ein „Rest” (das B), den man noch verarbeiten
muss. Es genügt, sich die „Ausstiegsstelle” eines Knoten (und den damit noch zu bearbeitenden
Rest) zu merken, die dann zum gegebenen Zeitpunkt als Wiedereinstiegsstelle dient. Dies
geschieht mittels eines Stapels (engl.: stack), auch Keller (pushdown) genannt.
93
Ein Kellerautomat ist also ein um einen Keller erweiterter nichtdeterministischer endlicher
Automat. Man darf nur immer auf das zuletzt „gemerkte Zeichen” zugreifen, die sogen. LIFOStrategie. Ein Zustandsübergang (und damit eine Konfigurationsänderung) erfolgt in Abhängigkeit des aktuellen Zustandes, der Eingabe- und dem obersten Kellersymbol. „Oberstes” Kellersymbol wird aus schreibtechnischen Gründen im Folgenden auch mal das „am weitesten links
bzw. rechts stehende” oder das „unterste” Symbol. Es erfolgt nicht nur ein Zustandsübergang
und ein Weitergehen auf dem Eingabeband. Der Kellerautomat darf dabei nicht nur das oberste
Kellersymbol lesen, sondern er darf es auch löschen bzw. ein weiteres Zeichen dafür in den
Keller schreiben.
Wie beim endlichen Automaten in der Erscheinungsform als Moore- oder Mealy-Automat,
kann der Kellerautomat auch so definiert werden, dass er Ausgaben produziert.
Definitionen:
Ein (nichtdeterministischer) Kellerautomat mit Ausgabe KA ist ein 8-Tupel
KA = (
Σ
∆
Z
z0
E
Γ
=
δ
Eingabealphabet,
Ausgabealphabet,
Zustandsmenge,
Startzustand,
f Z Menge der Endzustände,
Kelleralphabet,
0 Γ, das Kellerende- / Kellerinitialisierungs-Symbol
Zustandsüberführungsfunktion
)
mit δ : (Z × (Σ c {g}) × Γ) 6 (Z × Γ* × ∆*), wobei also in einem Zustand unter Verbrauch
(oder auch nicht!) eines Eingabezeichens sowie eines Kellersymbols in einen Folgezustand
übergegangen wird und dabei Zeichenketten aus Γ* bzw. ∆* in den Keller bzw. auf die Ausgabe
geschrieben werden.
Zur Vereinfachung lassen wir die Mengenklammer weg, wenn δ(z, a, b) nur ein Tripel als
Ergebnis hat.
Im eine geeignete Sprechweise für „Berechnung durch einen Kellerautomaten” oder „Erkennung einer Zeichenkette durch einen Kellerautomaten” zu haben, braucht man wieder das
Konzept der Konfiguration. Eine Konfiguration ist ein Tupel
(
z
α
β
ω
0Z,
0 Σ* ,
0 Γ* ,
0 ∆* ,
der aktuelle Zustand,
die noch nicht gelesene Eingabe,
der Kellerinhalt,
die bereits produzierte Ausgabe
)
94
Sei im folgenden a 0 Σ c {g} und b 0 Γ und β1, β2 0 Γ* und α 0 Σ* sowie ω1, ω2 0 ∆*;
außerdem sei z1, z2 0 Z. Eine Konfiguration k2 ist Nachfolgekonfiguration von k1, i.Z. k1 | k2,
gdw.
k1 = (z1, aα, bβ1, ω1) und k2 = (z2, α, β2β1, ω1ω2) und (z2, β2, ω2) 0 δ(z1, a, b)
Die Ausgabe eines Kellerautomaten interessiert meist nur bei den praktischen Anwendungen,
wenn der Automat nicht nur die Ausgabe „ja” bzw. „nein” machen soll, also das zu untersuchende Wort Element der Sprache bzw. nicht ist, sondern ggf. auch mitteilen soll, welche Produktionen angewendet wurden. Wenn dies irrelevant ist, lassen wir im Folgenden bei manchen
Beispielen, um sie einfacher zu halten, die Ausgabekomponente weg.
Die Erkennung eines Wortes α beginnt in der Startkonfiguration (z0, α, =, g). Für das Erkennen
eines Wortes durch einen Kellerautomaten hat man zwei Möglichkeiten der Definition. (Natürlich muss die Eingabe in beiden Fällen abgearbeitet sein.):
-
Erkennung durch ausgezeichneten Zustand zf 0 E, d.h. der Keller muss dabei nicht leer
sein.
-
Erkennung durch leeren Keller. Dann verzichtet man aber auf ausgezeichnete Zustände,
d.h. man macht E = Z. Diese Variante ist die übliche, insbesondere bei praktischen
Anwendungen. Man kann sogar beweisen, dass man mit einem einzigen Zustand auskommt.
Es wird sich zeigen, dass die beiden Varianten äquivalent sind.
Zunächst beschäftigen wir uns mit der ersten:
Definition:
Sei K = (Σ, ∆, Z, z0, E, Γ, =, δ) ein Kellerautomat. Dann ist die von K erkannte Sprache LE(K)
= {w 0 Σ* | (z0, w, =, g) |* (zf, g, γ, ω), zf 0 E, γ 0 Γ*, ω 0 ∆*}
Ê
95
Zur Veranschaulichung soll folgende Graphik dienen:
Zustandsübergang von q1 nach q2, Eingabesymbol a, oberstes Kellersymbol b, eingekellert wird dafür β2, ausgegeben wird ω2
Beispiel:
Betrachten wir die klassische kontextfreie Sprache anbn mit n $0. Wie könnte ein Kellerautomatenprogramm zur Erkennung einer Zeichenkette ausschauen, die diese Form hat?
Lösung: Man könnte quasi in einer „Laufschleife” die a einlesen, sie im Keller speichern und
dann für jedes gelesene b ein a herausstreichen. Der Kellerautomat K hat folgende Gestalt:
K = ({a, b}, i, {z0, z1, zf}, {zf}, z0, {a, =}, =, δ), wobei δ (ohne Ausgabe) wie folgt definiert ist:
δ(z0, g, =)
δ(z0, a, =)
δ(z0, a, a)
δ(z0, b, a)
δ(z1, b, a)
δ(z1, g, =)
=
=
=
=
=
=
(zf, g)
(z0, a=)
(z0, aa)
(z1, g)
(z1, g)
(zf, g)
(leeres Wort wird akzeptiert)
(Einlesen des ersten a)
(Einlesen der restlichen a)
(Behandlung des ersten b)
(Behandlung der restlichen b)
(Schluss, wenn Eingabe leer)
Natürlich wäre noch zu beweisen, dass dieser Kellerautomat wirklich die Sprache anbn mit n
$0 erkennt.
Betrachten wir die Konfigurationen, die sich bei der Abarbeitung des Wortes a3b3 ergeben:
(z0, aaabbb, =) |
Ê
96
Beispiel:
Betrachten wir ein weiteres Beispiel, die Erkennung der Sprache wcwR mit w 0 {a, b}*.
Die δ-Funktion des zugehörigen analysierenden Kellerautomaten lautet:
Die Konfigurationenfolge bei der Analyse des Wortes abcba lautet:
(z0, abcba, =) |
Ê
97
Document
Kategorie
Seele and Geist
Seitenansichten
10
Dateigröße
183 KB
Tags
1/--Seiten
melden