close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

12 Wie kann man kontextfreie Sprachen noch charakte- risieren

EinbettenHerunterladen
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 aSB | , B ✂ 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,
✆ Z Menge der Endzustände,
Kelleralphabet,
✟ ✠ , das Kellerende- / Kellerinitialisierungs-Symbol
Zustandsüberführungsfunktion
)
✡
mit : (Z × ( ☛ ☞ { ✌ }) × ✍ ) ✎ ✏ (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
✛
✕
✘
✔ Z,
✖ ✗ *,
✙
✚ *,
✜ ✢
*,
der aktuelle Zustand,
die noch nicht gelesene Eingabe,
der Kellerinhalt,
die bereits produzierte Ausgabe
)
94
Sei im folgenden a ✣ ✤ ✥ { ✦ } und b ✣ ✧ und ★ 1, ★ 2 ✣ ✧ * und ✩ ✣ ✤ * sowie ✪ 1, ✪ 2 ✣ ✫ *;
außerdem sei z1, z2 ✣ Z. Eine Konfiguration k2 ist Nachfolgekonfiguration von k1, i.Z. k1 ✬ k2,
gdw.
k1 = (z1, a ✭ , b ✮ 1, ✯
) und k2 = (z2, ✭ , ✮ 2 ✮ 1, ✯
1
1
✯ 2) und (z2, ✮ 2, ✯ 2) ✰ ✱ (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, ✭ , ✲ , ✳ ). 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 ✰ 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 ✰ ✴ * | (z0, w, ✲ , ✳ ) ✷ * (zf, ✸ , ✹ , ✺ ), zf ✻ E, ✹ ✻ ✼ *, ✺ ✻ ✽ *}
✾
95
Zur Veranschaulichung soll folgende Graphik dienen:
Schritt von q1 nach q2; Eingabe a, Kellersymbol b
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}, ❀ , {z0, z1, zf}, {zf}, {a, ❁ }, ❂ ), wobei ❂ (ohne Ausgabe) wie folgt definiert ist:
❂ (z0, ❃ , ❁ )
❂ (z0, a, ❁ )
❂ (z0, a, a)
❂ (z0, b, a)
❂ (z1, b, a)
❂ (z1, ❃ , ❁ )
=
=
=
=
=
=
(zf, ❃ )
(z0, a ❁ )
(z0, aa)
(z1, ❃ )
(z1, ❃ )
(zf, ❃ )
(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 Spiegelsprache wcwR mit w ❇ {a, b}*.
Die ❈ -Funktion des zugehörigen analysierenden Kellerautomaten lautet:
Die Konfigurationenfolge bei der Analyse des Wortes abcba lautet:
(z0, abcba, ❉ ) ❊
❋
97
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 ● {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, ■ ) ❏
❑
98
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
L◗ (K) = {w ❘ ❙ * | (z0, w, ❚ , ❯ ) ❱ * (z, ❯ , ❯ , ❲ ), z ❘ Z, ❲
❘ ❳ *}
❨
Satz:
Die Klasse der Sprachen ❩ E über einem Alphabet ❬ , die durch Kellerautomaten mit erkennenden Zuständen akzeptiert werden, ist gleich der Klasse der Sprachen ❩ ❭ über ❬ , die durch
Kellerautomaten mit leerem Keller akzeptiert werden.
Beweis(idee):
Sei L ❪ ❩ E eine Sprache, die von einem Kellerautomaten KE = ( ❬ , ❫ , Z, z0, E, ❴ , ❵ , ❛ )
akzeptiert wird. Zu KE wird ein äquivalenter Kellerautomat K❭ = ( ❬ , ❫ , Z ❜ {z0', ze}, z0', ❝ , ❴
❜ { ❞ }, ❞ , ❡ ') konstruiert, der ebenfalls L erkennt, wobei für ❡ ' noch folgendes gilt:
❢
❢
K❣ geht von seinem eigenen Startzustand in den von KE über, also ❤ '(z0', ✐ , ❥ ) =
(z0, ❦❧❥ ).
❢
Jetzt simuliert K❣ die Arbeit von KE.
Gelangt KE in einen Endzustand e ♠ E (bei leerer Eingabe), muss K❣ seinen
Keller
leeren, also wird zu ❤ ' noch hinzugenommen: ❤ '(e, ✐ , k) = (ze, ✐ ) für k ♠
♥
♦ {❥ }
Sei
♥ nun umgekehrt L ♠ ♣ ❣ eine Sprache, die durch einen Kellerautomaten K❣ = ( q , r , Z, z0,
E, , ♥ ❦ , ❤ ) akzeptiert wird. Zu K❣ wird ein äquivalenter Automat KE = ( q , r , Z ♦ {z0', ze}, z0',
{ze}, ♦ { ❥ }, ❥ , ❤ ') konstruiert, der ebenfalls L erkennt, wobei für ❤ ' noch folgendes gilt:
❢
❢
KE geht von seinem eigenen Startzustand in den von K❣ über, also ❤ '(z0', ✐ , ❥ ) =
(z0, ❦❧❥ ).
❢
Jetzt simuliert KE die Arbeit von K❣ .
Hat K❣ seinen Keller einschließlich ❦ gelöscht, steht noch ❥ im Keller. Jetzt
muss KE nur noch in den Endzustand ze mittels ❤ '(z, ✐ , ❥ ) = (ze, ✐ ) übergehen.
s
99
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. 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, t , P, S) gibt es einen äquivalenten Kellerautomaten
K = ( ✉ , ✈ , {z}, z, ✇ , V ① t , S, ② ) mit L(G) = L(K).
Beweis:
Zunächst sei für die Grammatik S ③ aSbS | aS | c , die Ausgangspunkt unserer Überlegungen
war, das Konstruktionsverfahren verdeutlicht: ② muss für den äquivalenten Kellerautomaten so
konstruiert werden:
② (z, ④ , S)
② (z, a, a)
② (z, b, b)
② (z, c, c)
=
=
=
=
{(z, aSbS, 1), (z, aS, 2), (z, c, 3)}
(z, ④ , ④ )
(z, ④ , ④ )
(z, ④ , ④ )
Wie man sieht, kommt man mit einem Zustand aus.
Allgemein: Ist das oberste Kellersymbol ein Nichtterminal, wird ein ④ -Übergang gemacht und
die rechten Seiten in den Keller geschrieben. Für ein A ③ ⑤ kommt der Übergang ② (z, ④ , A) =
(z, ⑤ ) hinzu. Außerdem wird für jedes Terminalsymbol a der Übergang ② (z, a, a) = (z, ④ )
aufgenommen, wobei hier wieder auf Ausgaben verzichtet wurde.
Ein solcher Automat simuliert also die Linksableitungen der Grammatik und es ist unschwer
⑥
einzusehen, dass L(G) = L(K).
100
Document
Kategorie
Seele and Geist
Seitenansichten
10
Dateigröße
129 KB
Tags
1/--Seiten
melden