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 ein Wort ab einer bestimmten Länge auch immer in 5 Teile zerlegt, die u.a. Varianten sind
nach beliebigem “Aufpumpen” 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. Damit 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
Bei den regulären Sprachen gab es mit dem Satz von Myhill und Nerode oder dem Lemma von
Jaffe Aussagen über notwendige und hinreichende Bedingungen dafür, dass eine Sprache regulär
ist. Bei den kontextfreien Sprachen gibt es mit dem Satz von Chomsky/Schützenberger eine
Aussage, die deutlich hilfreicher ist als die vorhergehenden. Dazu zunächst zwei Definitionen:
Ein Homomorphismus ist eine Abbildung h : A1 6 A2* zwischen zwei Alphabeten A1 und A2.
Dabei gilt h(u@v) = h(u)@h(v). Man kann zeigen, dass die Klasse der kontextfreien Sprachen
abgeschlossen ist gegenüber Homomorphismen.
Dyck-Sprachen sind die “Klammersprachen” und vom Typ kontextfrei. Genauer kann man es
so fassen. Seien G, G1 und G2 Alphabete mit G = G1 c G2 und G1 1 G2 = i. Sei d : G1 6 G2 eine
eineindeutige Abbildung. Sei R eine Menge von Ableitungsregeln R = { a@a’ 6 ε | a 0 G1 v a’
= d(a) 0 G2 }. Die Menge aller zu ε reduzierbaren Wörter σ 0 G*, also σ Y* ε heißt DyckSprache über G. Gilt |G| = n, dann schreibt man auch Dn.
Satz von Chomsky/Schützenberger (ohne Beweis):
Jede Sprache L f G* ist genau dann kontextfrei, wenn sie das homomorphe Bild des Durchschnitts einer regulären Sprache R mit einer Dyck-Sprache D ist, also L = h(R 1 D) gilt.
Ê
Anschaulich könnte man den Satz so interpretieren: Wenn man eine Sprache vorgelegt
bekommt, eine Obermenge von ihr als regulären Ausdruck beschreiben könnte, und noch
erkennt, dass bei geeigneter Interpretation (also der Anwendung eines Homomorphismus) eine
Art Klammerstruktur vorliegt, dann ist die Sprache kontextfrei.
Übrigens, der Durchschnitt einer kontextfreien mit einer regulären Sprache ist kontextrei.
Beispiel:
91
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:
92
Behauptung:
Die kontextfreien Sprachen sind nicht abgeschlossen unter Komplement Σ* \ L und Durchschnitt L1 1 L2 .
Beweis:
93
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.
94
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
)
95
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 ∆*}
Ê
96
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}, z0, {zf}, {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, =) |
Ê
97
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, =) |
Ê
98
Beispiel:
Wir betrachten nun eine Variante des obigen Beispiels, bei der der „Spiegel” c wegfällt, oder
anders ausgedrückt, die Sprache aller geradzahligen Palindrome wwR mit w 0 {a, b}*. Das
Problem, das sich hier auftut, ist die Frage, wie man entscheiden kann, ob man in der Mitte ist
(natürlich ohne das Wort in seiner Gesamtheit vorverarbeitet zu haben). Die Antwort ist Nichtdeterminismus, d.h. man „errät” die Mitte. Analog zum nichtdeterministischen endlichen
Automaten wird auch beim Kellerautomaten nur gefordert, dass eine Folge von Konfigurationen
existieren muss, um von der Startkonfiguration in einen erkennenden Endzustand zu kommen.
Es wird dabei nicht angegeben, wie man sackgassenfrei dorthin gelangt. Ggf. muss man Backtracking in Kauf nehmen und alle Alternativen durchprobieren.
Die δ-Funktion des zugehörigen analysierenden Kellerautomaten lautet:
Ein Analyseversuch könnte folgende Konfigurationenfolge erzeugen:
(z0, abbbba, =) |
Ein weiterer diese:
(z0, abbbba, =) |
Ê
99
Wie bereits zu Beginn dieses Kapitels erwähnt, kann man die Erkennung von kontextfreien
Sprachen durch Kellerautomaten ohne ausgezeichnete erkennende Zustände auch über die
Erkennung mit leerem Keller definieren.
Definition:
Sei K = (Σ, ∆, Z, z0, E, Γ, =, δ) ein Kellerautomat. Dann ist die von K erkannte Sprache
Lg(K) = {w 0 Σ* | (z0, w, =, g) |* (z, g, g, ω), z 0 Z, ω 0 ∆*}
Ê
Satz:
Die Klasse der Sprachen ‹E über einem Alphabet Σ, die durch Kellerautomaten mit erkennenden Zuständen akzeptiert werden, ist gleich der Klasse der Sprachen ‹g über Σ, die durch
Kellerautomaten mit leerem Keller akzeptiert werden.
Beweis(idee):
Sei L 0 ‹E eine Sprache, die von einem Kellerautomaten KE = (Σ, ∆, Z, z0, E, Γ, =, δ) mit
erkennenden Zuständen akzeptiert wird. Zu KE wird ein äquivalenter Kellerautomat Kg = (Σ, ∆,
Z c {z0', ze}, z0', i, Γ c {‚}, ‚, δ') konstruiert, der mit leerem Keller ebenfalls L erkennt, wobei
für δ' noch folgendes gilt:
C
Kg geht von seinem eigenen Startzustand in den von KE über, also δ'(z0', g, ‚) =
(z0, =‚).
C
Jetzt simuliert Kg die Arbeit von KE.
C
Gelangt KE in einen Endzustand e 0 E (bei leerer Eingabe), muss Kg seinen
Keller leeren, also wird zu δ' noch hinzugenommen: δ'(e, g, k) = (ze, g) für k 0 Γ
c {‚}
Sei nun umgekehrt L 0 ‹g eine Sprache, die durch einen Kellerautomaten Kg = (Σ, ∆, Z, z0, E,
Γ, =, δ) mit leerem Keller akzeptiert wird. Zu Kg wird ein äquivalenter Automat KE = (Σ, ∆, Z
c {z0', ze}, z0', {ze}, Γ c {‚}, ‚, δ') konstruiert, der mit erkennenden Zuständen ebenfalls L
erkennt, wobei für δ' noch folgendes gilt:
C
KE geht von seinem eigenen Startzustand in den von Kg über, also δ'(z0', g, ‚) =
(z0, =‚).
C
Jetzt simuliert KE die Arbeit von Kg.
C
Hat Kg seinen Keller einschließlich = gelöscht, steht noch ‚ im Keller. Jetzt muss
KE nur noch in den Endzustand ze mittels δ'(z, g, ‚) = (ze, g) übergehen.
Ê
100
Wie wir gesehen haben, ist das Akzeptieren eines Wortes durch leeren Keller oder durch
erkennende Zustände bei Kellerautomaten gleichwertig. Wir müssen uns aber vergegenwärtigen,
dass wir bislang immer von der Annahme ausgehen, dass es sich um nichtdeterministische
Kellerautomaten handelt. Es gibt nicht zu jedem deterministischen (!) Kellerautomaten, der mit
ausgezeichnetem Endzustand erkennt, auch einen deterministischen Kellerautomaten, der mit
leerem Keller erkennt. Hinzu kommt, dass man nicht zu jedem nichtdeterministischen Kellerautomaten einen äquivalenten deterministischen Kellerautomaten - unabhängig von der Art der
Erkennung - finden kann. Bevor wir auf die unterschiedlichen Fähigkeiten von nichtdeterministischen und deterministischen Kellerautomaten eingehen und auch noch die Unterschiedlichkeit beim Determinismus behandeln, soll hier auf die Äquivalenz zwischen kontextfreien
Grammatiken und (nichtdeterministischen) Kellerautomaten eingegangen werden.
Satz:
Zu jeder kontextfreien Grammatik G = (V, G, P, S) gibt es einen äquivalenten Kellerautomaten
K = (Σ, ∆, {z}, z, i, V c G, S, δ) mit L(G) = L(K).
Beweis:
Zunächst sei für die Grammatik S 6 aSbS | aS | c , die Ausgangspunkt unserer Überlegungen
war, das Konstruktionsverfahren verdeutlicht: Der relevante Teil von δ muss für den äquivalenten Kellerautomaten so konstruiert werden:
δ(z, g, S)
δ(z, a, a)
δ(z, b, b)
δ(z, c, c)
=
=
=
=
{(z, aSbS, 1), (z, aS, 2), (z, c, 3)}
(z, g, g)
(z, g, g)
(z, g, g)
Wie man sieht, kommt man mit einem Zustand aus.
Allgemein: Ist das oberste Kellersymbol ein Nichtterminal, wird ein g-Übergang gemacht und
die rechten Seiten in den Keller geschrieben. Für ein A 6 α kommt der Übergang δ(z, g, A) = (z,
α,<Produktionsnummer>) hinzu. Außerdem wird für jedes Terminalsymbol a der Übergang δ(z,
a, a) = (z, g, g) aufgenommen, wobei hier keine Produktionsnummer in die Ausgabe geschrieben
wird.
Ein solcher Automat simuliert also die Linksableitungen der Grammatik und es ist unschwer
einzusehen, dass L(G) = L(K).
Ê
An dem Beispiel wird u.a. folgendes ersichtlich: Die dritte Komponente der Tripel aus dem
Wertebereich von δ ermöglicht , dass nicht nur eine ja/nein-Entscheidung bei der Analyse eines
Wortes getroffen werden kann, sondern auch eine Angabe darüber, in welcher Reihenfolge die
Produktionen angewendet werden müssen, um ein Wort w zu generieren. Dies ist bei praktischen Anwendungen sehr wichtig.
101
Jetzt der etwas schwierigere Fall:
Satz:
Zu jedem Kellerautomaten K = (Σ, ∆, Z, z0, E, Γ, =, δ) gibt es eine kontextfreie Grammatik G
= (V, G, P, S) mit L(K) = L(G).
Beweis(idee):
Der Einfachheit halber betrachten wir nur Kellerautomaten ohne Ausgabe und ohne erkennende Zustände, somit E = i = ∆, also solche Kellerautomaten, die durch leeren Keller akzeptieren.
Der grundlegende Gedanke bei der Konstruktion für G ist, dass K bei der Analyse eines
Wortes Symbole aus seinem Keller entfernt, während er von der Eingabe liest. (Am Anfang
steht das Kellerinitialisierungs-Symbol im Keller, das entfernt werden muss, bis das Ende der
Eingabe erreicht ist. Zwischenstationen kann man auch so sehen.) Bei der Entfernung des
obersten Kellersymbols γ kann es zunächst in ein anderes Symbol γ' verwandelt werden, das
wiederum durch γ''γ''' ersetzt wird. Nachfolgende Bewegungen würden - ggf. über weitere
Zwischenstationen - γ'' und dann γ''' entfernen, insgesamt also ist das γ verschwunden. Während
K dies tut, hat er eine Zeichenkette u analysiert und ist dabei i.A. durch verschiedene Zustände startend bei z und endend bei z' - gegangen, die man sich durch die zu konstruierenden Nichtterminale bzw. Produktionen merken muss.
Ein Nichtterminal habe die Gestalt [z, γ, z']. Aus einem solchen sollen genau die Zeichenketten
u 0 Σ* ableitbar sein, bei deren Analyse K vom Zustand z mit oberstem Kellersymbol γ in den
Zustand z' geht, also
[z, γ, z'] Y*G u ] (z, u, γ) |*K (z', g, g)
Demnach ist L(K) ist die Menge aller Wörter w 0 Σ*, für die (z0, w, =) | (z', g, g) gilt, mit z' 0
Z. Wenn wir nun alle Regeln der Art S 6 [z0, =, z'] für z' 0 Z zu P hinzunehmen, gilt schließlich
w 0 L(K) ] S Y*G w
S erzeugt letztlich also alle Zeichenreihen w, die K dazu bringen, den Keller bei der Abarbeitung von w zu leeren, wenn er in der Startkonfiguration (z0, w, =) beginnt.
102
Die Konstruktion für die Grammatik verläuft folgendermaßen:
In V stecken wir ein ausgezeichnetes Nichtterminal, das bereits o.g. S. Außerdem nehmen wir
alle Nichtterminale der Form [z, γ, z'] mit z, z' 0 Z und γ 0 Γ zu V hinzu.
Zusätzlich zu den obigen Produktionen für S der Art S 6 [z0, =, z'] für alle z' 0 Z brauchen wir
noch weitere:
Fall 1: Sei δ(z, a, γ) h (z', g) mit a 0 Σ c {g}.
Dann gilt (z, a, γ) | (z', g, g) und wir nehmen die Produktion [z, γ, z'] 6 a in P auf.
Fall 2: Sei δ(z, a, γ) h (z1, γ1γ2...γk) mit a 0 Σ c {g} und 1 # k. (Der Fall k = 0 ist der obige.)
Für ein u = au1u2...uk gibt es eine Folge von Zuständen z1, z2, ..., zk, sodass die Analyse
(z, au1u2...uk, γ) | (z', g, g)
zerlegt werden kann in
(z, au1u2...uk, γ) | ( z1, u1u2...uk, γ1γ2...γk) |* (z2, u2...uk, γ2...γk) |* ... |* (zk, uk, γk) |* (z', g, g)
Die γ1γ2...γk, die beim ersten Schritt in den Keller gelegt werden, müssen, wie eingangs bereits
erklärt, wieder entfernt werden, wobei irgendwelche Zustände z1, z2, ..., zk auftreten, die man
nicht im Voraus kennt, für die es aber nur endlich viele Möglichkeiten gibt. Für jede Folge z2,
..., zk von k - 1 Zuständen wird beim Vorliegen von δ(z, a, γ) h (z1, γ1γ2...γk) die folgende
Produktion in P aufgenommen:
[z, γ, z'] 6 a[z1, γ1, z2][z2, γ2, z3] ... [zk-1, γk-1, zk][zk, γk, z']
Die Nichtterminale von G und die Produktionen sind also so definiert, dass eine Linksableitung von G für ein (Teil-)Wort u eine Simulation von K ist, wenn K mit u im Zustand z und
oberstem Kellersymbol γ gestartet wurde und in z' übergeht. Insbesondere entsprechen die
Nichtterminale, die im Schritt einer Linksableitung auftauchen, jeweils den Symbolen auf dem
Keller zu dem Zeitpunkt, zu dem K das analysiert, was G dabei generiert.
Es ist über Induktion noch zu beweisen, dass die Interpretation der Nichtterminale [zi, γ, zj]
auch korrekt ist, was aber hier nicht weiter geschehen soll.
Ê
103
Beispiel (nach Hopcroft/Ullman):
Sei K = ({0, 1}, i, {z0, z1}, z0, i, {A, B}, A, δ) mit δ definiert als:
δ(z0, 0, A) = (z0, BA)
δ(z0, 0, B) = (z0, BB)
δ(z0, 1, B) = (z1, g)
δ(z1, 1, B) = (z1, g)
δ(z1, g, B) = (z1, g)
δ(z1, g, A) = (z1, g)
Die Menge der Nichtterminale ist dann zunächst
V = {S, [z0, A, z0], [z0, A, z1], [z1, A, z0], [z1, A, z1], [z0, B, z0], [z0, B, z1], [z1, B, z0],
[z1, B, z1]}.
Die Menge der Produktionen besteht erst aus
S 6 [z0, A, z0]
S 6 [z0, A, z1]
Wir fügen hinzu die Produktionen für δ(z0, 0, A) = (z0, BA), also
[z0, A, z0] 6 0 [z0, B, z0] [z0, A, z0]
[z0, A, z0] 6 0 [z0, B, z1] [z1, A, z0]
[z0, A, z1] 6 0 [z0, B, z0] [z0, A, z1]
[z0, A, z1] 6 0 [z0, B, z1] [z1, A, z1]
Wegen δ(z0, 0, B) = (z0, BB) kommen noch folgende Produktionen hinzu:
[z0, B, z0] 6 0 [z0, B, z0] [z0, B, z0]
[z0, B, z0] 6 0 [z0, B, z1] [z1, B, z0]
[z0, B, z1] 6 0 [z0, B, z0] [z0, B, z1]
[z0, B, z1] 6 0 [z0, B, z1] [z1, B, z1]
Wegen δ(z0, 1, B) = (z1, g), δ(z1, 1, B) = (z1, g), δ(z1, g, B) = (z1, g) und δ(z1, g, A) = (z1, g) die
Produktionen
[z0, B, z1] 6 1
[z1, B, z1] 6 g
[z1, B, z1] 6 1
[z1, A, z1] 6 g
104
Wir versuchen nun, die Grammatik zu reduzieren: Wie man gleich sieht, gibt es für die
prophylaktisch gebildeten Nichtterminale [z1, B, z0] und [z1, A, z0] keine Produktionen. Deshalb
kann man alle Produktionen oben mit diesen Nichtterminalen auf der rechten Seite eliminieren.
Dann bleiben zunächst:
S
S
[z0, A, z0]
[z0, A, z1]
[z0, A, z1]
[z0, B, z0]
[z0, B, z1]
[z0, B, z1]
[z0, B, z1]
[z1, B, z1]
[z1, B, z1]
[z1, A, z1]
6 [z0, A, z0]
6 [z0, A, z1]
6 0 [z0, B, z0] [z0, A, z0]
6 0 [z0, B, z0] [z0, A, z1]
6 0 [z0, B, z1] [z1, A, z1]
6 0 [z0, B, z0] [z0, B, z0]
6 0 [z0, B, z0] [z0, B, z1]
6 0 [z0, B, z1] [z1, B, z1]
61
6g
61
6g
Wie man sieht, sind auch die kursiv geschriebenen Produktionen problematisch, weil sie nicht
zu terminalen Zeichenketten führen. Deshalb lautet die vereinfachte Grammatik
S
[z0, A, z1]
[z0, B, z1]
[z0, B, z1]
[z1, B, z1]
[z1, B, z1]
[z1, A, z1]
6 [z0, A, z1]
6 0 [z0, B, z1] [z1, A, z1]
6 0 [z0, B, z1] [z1, B, z1]
61
6g
61
6g
die man weiter zu
S
[z0, B, z1]
[z1, B, z1]
6 0 [z0, B, z1]
6 0 [z0, B, z1][z1, B, z1] | 1
61|g
umschreiben kann.
Ê
Bemerkung:
Zusammenfassend lässt sich also sagen, dass die folgenden drei Aussagen äquivalent sind:
>
L ist eine kontextfreie Sprache, d.h. sie wird durch eine kontextfreie Grammatik erzeugt.
>
L ist eine Sprache, die von einem Kellerautomaten mit erkennenden Zuständen akzeptiert
wird.
>
L ist eine Sprache, die durch einen Kellerautomaten mit leerem Keller akzeptiert wird.
105
Document
Kategorie
Seele and Geist
Seitenansichten
15
Dateigröße
212 KB
Tags
1/--Seiten
melden