close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

7 Wie kann man reguläre Sprachen noch beschreiben (Reguläre

EinbettenHerunterladen
7
Wie kann man reguläre Sprachen noch beschreiben
(Reguläre Ausdrücke)?
So wie die EBNF im Vergleich zu den kontextfreien Grammatiken den Umgang mit kontextfreien Sprachen erleichtert, vereinfachen reguläre Ausdrücke oft die Arbeit mit regulären Sprachen. Sie sind ist ein drittes Konzept zur Charakterisierung von regulären Sprachen neben dem
DEA mit seinen Varianten und den einseitig linearen Grammatiken. Diese neue Charakterisierung gleicht mehr der Beschreibung von Sprachen durch Mengen mit bereits bekannten, auf
Mengen definierten Operationen.
Ausgehend vom einem Alphabet Σ bei dem jedes Element a 0 Σ die Sprache {a} repräsentiert,
werden drei Operatoren eingeführt, um komplexere Zeichenkettenmengen zu definieren: Konkatenation, Alternative, Abschluss.
Definition:
Reguläre Ausdrücke werden rekursiv definiert.
1)
Die leere Menge i ist ein regulärer Ausdruck (der als Sprache die leere Menge hat).
2)
Das leere Wort g ist ein regulärer Ausdruck mit der Menge als Sprache, die aus dem
leeren Wort besteht.
3)
Ein a 0 Σ ist ein regulärer Ausdruck mit {a} als Sprache.
4)
Sind e, e1 und e2 reguläre Ausdrücke mit den zugehörigen Sprachen L, L1 bzw. L2, dann
sind die folgenden Ausdrücke auch reguläre Ausdrücke mit den assoziierten Sprachen:
(e)
:= L (d.h. einfach, man darf Klammern setzen)
e1 | e 2
:= L1 c L2 = {x | x 0 L1 w x 0 L2} (Alternative, manchmal auch Vereinigung genannt und manchmal auch mit „+” bezeichnet):
e 1e 2
:= L1 B L2 = {xy | x 0 L1 v y 0 L2} (Konkatenation, manchmal auch
Produkt oder Sequenz genannt, wobei B meist weggelassen wird)
e*
:= L* = {x | x 0 L*} (Abschluss, manchmal auch Kleene'sche SternOperation oder Iteration genannt)
5)
i* = {g}
Ê
Bemerkungen:
Der syntaktische Teil der obigen Definition für reguläre Ausdrücke A über einem Alphabet Σ
= {a1, a2, ..., an} ließe sich auch kurz mit
A 6 i | g | a1 | a2 | ... | an | AA | A+A | A* | (A)
notieren.
Die Syntax regulärer Ausdrücke darf nicht mit der EBNF verwechselt werden. Z.B. fehlt bzgl.
der EBNF die Option "[ ]", die auch gestattet, keine der Alternativen zu wählen. Das "|" verlangt
mindestens eine Alternative. Außerdem verwendet die EBNF Nichtterminale.
Ê
63
Prioritätsregeln machen die regulären Ausdrücke einfacher:
*
B
|
höchste Priorität
mittlere Priorität
unterste Priorität,
also ist ((p) | ((p)(q))) kürzer durch p | pq darstellbar.
Mit regulären Ausdrücken lässt sich auch "rechnen". Z.B. gelten folgende Regeln:
(e1e2)e3 = e1(e2e3)
(e1 | e2) | e3 = e1 | (e2 | e3)
e1 | e2 = e 2 | e 1
e1(e2 | e3) = e1e2 | e1e3
"Assoziativgesetz"
"Assoziativgesetz"
"Kommutativgesetz"10
"Distributivgesetz"
Beispiele:
1.
a*b*
= { ambn | m, n $ 0}
2.
(ab)*
= {(ab)m | m $ 0}
3.
(a | b)*
= {x | x 0 {a, b}*}
4.
(aa | ab | ba | bb)*
= {x | x 0 {a, b}* und |x| geradzahlig}
5.
Identifikatoren in Programmiersprachen:
S 6 aA | bA | cA | ... | zA | a | b | ... | z
A 6 aA | bA | cA | ... | zA | 0A | 1A | ... | 9A | a | b | ... | z | 0 | 1 | 2 | ... | 9
Einfacher zu beschreiben durch den regulären Ausdruck:
(a | b | c | ... | z) ( a | b | c | ... | z | 0 | 1 | ... | 9 )*
Ê
10
Natürlich gilt ab … ba .
64
Betrachte die folgende Grammatik:
S 6 a S | aB
B 6 bB | bC
C 6 aC | a
Der Sachverhalt, den sie beschreibt, ist schlicht folgender: „Betrachte Zeichenketten, die mit
einem oder mehreren a's beginnen, gefolgt von einem oder mehreren b's, auf die dann wieder ein
oder mehrere a's folgen.”
Dies lässt sich viel eleganter durch einen zu ihr äquivalenten regulären Ausdruck darstellen:
aa*bb*aa* .
Natürlich lässt sich schnell ein äquivalenter NEA dazu angeben, wobei es am einfachsten ist,
von der Grammatik auszugehen, wenn sie schon wie hier in einfacher Form vorliegt:
65
Als weiteres Beispiel betrachte man den regulären Ausdruck aa*(b | c)d*. Das zugehörige Zustandübergangsdiagramm des äquivalenten NEAg hat folgende Gestalt.
Die vorangegangenen Beispiele haben bereits Hinweise gegeben, dass es sich bei den Endlichen Automaten mit ihren Varianten, den einseitig linearen Grammatiken und den hier behandelten regulären Ausdrücken um äquivalente Konzepte zur Beschreibung regulärer Sprachen
handelt. Während es nicht ganz so leicht ist, aus einer vorgegebenen Grammatik den regulären
Ausdruck systematisch zu generieren, ist es vergleichweise einfach, zu einem regulären Ausdruck einen äquivalenten NEAg zu konstruieren.
66
Dazu baut man sukzessive aus den Bestandteilen des regulären Ausdrucks quasi von „innen
nach außen” den Automaten auf:
Automat zur Alternative (r1 | r2)
Automat zur Konkatenation r1 r2
67
Automat zur Iteration r*
Automat zum Terminalsymbol t
Startgraph
68
Beispiel:
Betrachten wir den regulären Ausdruck 0 (1 | (23))*. Eine syntaktische Analyse, die man am
besten durch einen Syntaxbaum darstellt, ergibt, dass es sich um eine Sequenz einer Iteration
einer Alternative handelt, die aus einem „elementaren” Terminalsymbol 1 und einer Sequenz
zweier Terminalsymbole 2 bzw. 3 besteht. Im u.a. Automaten erfolgt die Erkennung von 2 in
einem Zustand A, die von 3 in B. Die Sequenz aus 2 und 3 braucht wegen der Systematik einen
Zustand C. 1 korrespondiert zu D, die Alternative ...|... zu E, die Iteration (...)* zu F, 0 zu G und
schließlich die Komposition äußere Sequenz zu H.
NEAg zum regulären Ausdruck 0 (1 | (23))*
69
Wir wissen, dass man die g-Übergänge auf der Grundlage der g-Hüllenbildung aus einem
Automaten entfernen kann. Wie dies geht, soll noch einmal an diesem Beispiel verdeutlicht
werden.
Zur Erinnerung: Unter der g-Hülle eines Zustands z versteht man die Menge H(z) aller von z
aus durch möglicherweise wiederholte g-Übergänge erreichbaren Zustände einschließlich z
selbst. Man lässt den Automaten quasi die g-Übergänge „weiterticken“, bis er bei „echten“
Eingabesymbolen Halt macht und sammelt die dabei erreichten Zustände in einer Menge auf.
Wie aus dem Beispiel ersichtlich, ist z.B. die g-Hülle von S die Zustandsmenge {S, G, H}, die
man gewöhnlich durch [SGH] (oder durch eine Permutation wie [GHS]) notiert. Ein solcher
„Sammelzustand“ wird als neuer Zustand des zu konstruierenden äquivalenten endlichen
Automaten ohne g-Übergänge aufgefasst.
Jeder Sammelzustand Z wird für ein Element a des Eingabealphabets nach Nachfolgezustandsmengen untersucht. Ist z 0 Z und ist z' 0 δ(z, a), muss auch noch H(z') zur neuen Sammelzustandsmenge hinzugenommen werden.
Die Ergebnisse werden in einer Tabelle notiert.
0
1
2
3
[ACDEFF'G'H'#]
Null
i
i
i
[ACDEFF'G'H'#]
Null
i
[ACDD'EE'F'H'#]
Eins
[A'B]
Zwei
i
[ACDD'EE'F'H'#]
Eins
i
[ACDD'EE'F'H'#]
Eins
[A'B]
Zwei
i
[A'B]
Zwei
i
i
i
[ABCC'DEE'F'H'#]
Drei
[AB'CC'DEE'F'H'#]
Drei
i
[ACDD'EE'F'H'#]
Eins
[A'B]
Zwei
i
[GHS]
Start
In kursiver Schrift sind Namen mit mehr Semantik eingetragen. So bedeutet z.B. „Eins“ dass
„1 gesehen“ wurde. Die folgende Abbildung zeigt das äquivalente g-freie Zustandsübergangsdiagramm. Sammelzustände, die einen ursprünglichen erkennenden Zustand beinhalten, werden
zu neuen erkennenden Sammelzuständen.
70
Das Verfahren liefert uns den folgenden einfacheren Automaten:
Die g-freie Version des Automaten für den regulären Ausdruck
0(1| 23)*
aus dem man den folgenden Minimalautomat konstruieren kann:
Ê
71
Es wurde bereits gesagt, dass die Konstruktion des zu einer regulären Grammatik äquivalenten
Automaten nicht ganz einfach ist. Hier soll die allgemeine Beziehung behandelt werden:
Satz:
Zu jeder regulären Grammatik gibt es einen regulären Ausdruck, der dieselbe Sprache definiert.
Beweis(idee) durch Beispiel:
S 6 aS
S 6 aB
B 6 bC
C 6 aC
C6a
1. Schritt: "6" wird zu "=". Dann entsteht ein "Gleichungssystem"
S = aS | aB
B = bC
C = aC | a
2. Schritt: Die Gleichungen werden gelöst. Die Nichtterminale, die durch sich selbst definiert
sind, werden zuerst behandelt. Die Gleichung für C hat (vermutlich) die Lösung C = a*a, daraus
folgt der Ausdruck a*a = aa*a | a , für den die Gültigkeit des Gleichheitszeichens zu beweisen
ist. Dies ist leicht einzusehen, denn der reguläre Ausdruck der linken Seite steht für die Zeichenketten a, aa, aaa, ... . Der erste Teil der rechten Seite beschreibt die Zeichenketten aa, aaa, aaa,
... . Es fehlt also nur noch die Zeichenkette, die aus einem a besteht. Diese wird aber aus dem
zweiten regulären Ausdruck bestimmt. Also stimmt die geschätzte Lösung.
Eingesetzt in die anderen Gleichungen ergibt dies:
S = aS | aB
B = ba*a
7 (Lösung für B frei Haus geliefert)
Es bleibt
S = aS | aba*a
Durch analoge Überlegungen wie für C ergibt sich für S = a*aba*a
Ê
72
Allgemeines Verfahren
1.
Grammatik umschreiben in Gleichungsform:
Xi = δ1 | δ2 | ... | δm | ψjXj | ψkXk | ... | ψlXl
2.
Umschreiben zur Suche nach rekursiven Symbolen
Xn = αiXn | ψn | ...
Irgendeines mit dieser Eigenschaft wird ausgewählt. Die Lösung dafür ist von der Form:
Xn = αiαi*ψn. Gibt es kein rekursives Symbol, ist man fertig.
Xn = < was auch immer da steht >
ist Lösung
3.
Einsetzen der Lösung in alle anderen Gleichungen
2. und 3. solange wiederholen, bis alle Gleichungen gelöst sind.
Den Beweis, dass damit der zur Ausgangsgrammatik äquivalente reguläre Ausdruck konstruiert wird, schenken wir uns.
Ê
Die Umkehrung des Zusammenhangs zwischen regulären Ausdrücken und regulären Grammatiken gilt auch:
Satz:
Zu jedem regulären Ausdruck gibt es eine reguläre Grammatik.
Beweisidee durch ein Beispiel:
ab* (c | df*) lässt sich beschreiben durch die Grammatik:
S 6 a <R1>
<R2> 6 c
<R1> 6 b <R1>
<R2> 6 d <R3>
<R1> 6 <R2>
<R3> 6 f <R3> | g
Wie man unschwer sieht, geschieht die Umformung nach dem Prinzip:
Sequenz:
Iteration:
Alternative:
Terminalsymbol und einen "Rest"
durch rekursives Nichtterminal
durch |
Ê
73
Zusammenfassung:
Reguläre Ausdrücke sind nur eine andere, aber oft bequemere Form der Charakterisierung von Zeichenkettenmengen, die auch mit einseitig linearen Grammatiken
oder mit Endlichen Automaten beschreibbar sind. Die verschiedenen Darstellungen
lassen sich durch einfache Verfahren ineinander überführen.
74
8
Wie verhalten sich reguläre Sprachen zueinander?
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. Gibt es ein Kriterium, mit dem wir
entscheiden können, ob überhaupt Chancen bestehen oder ob es grundsätzlich keine reguläre
Grammatik dafür gibt? Wir suchen also nach notwendigen Eigenschaften, die alle regulären
Sprachen haben müssen. Hat eine Sprache nicht diese Eigenschaft, kann sie nicht regulär sein.
Ein Ansatz zum Finden eines solchen Kriteriums ist die Einsicht, dass Endliche Automaten
wegen der endlichen Zahl ihrer Zustände ein „endliches Gedächtnis” haben. Bei Eingaben, die
eine gewisse Größe überschreiten, können Wiederholungen nicht mehr von einander unterschieden werden.
Satz: („Pumping-Lemma” für reguläre Sprachen)
Sei M eine reguläre Sprache. Dann gibt ein n 0 ù, sodass sich jedes σ 0 M mit |σ| $ n so in
drei Teile zerlegen lässt, dass gilt: σ = uvw mit |v| $ 1, |uv| # n und (œi $ 0)(uviw 0 M).
Beweis(-ideen):
(1. Variante) Für M gibt es einen DEA A mit L(A) = M. Sei n die Zahl der Zustände von A
und x1x2...xm 0 L(A) mit m $ n. Bei der Abarbeitung von x wird die Zustandsfolge z0z1z2...zm durchlaufen, wenn z0 der Startzustand ist. Dabei gibt es notwendigerweise einen Zustand, der bei der Abarbeitung mindestens zweimal erreicht
wird, also zj = zk mit 0 # j < k #n. Wir setzen nun u = x1x2...xj, v = xj+1xj+2...xk
und w = xk+1xk+2...xm.
Es gilt |v| $ 1, da k > j und |uv| # n, da k # n. Damit sind die ersten beiden
Anforderungen erfüllt. Da δ*(zj, v) = zk = zj, gilt auch δ*(zj, vv) = zk = zj. Also
kann v beliebig oft iteriert werden und uviw 0 M
(2. Variante): Zu M gibt es eine Grammatik G mit L(G) = M. Wenn n genügend groß ist, muss
bei der Ableitung von σ mindestens ein Nichtterminal wiederholt auftreten, also
S Yj uY Yk-j+1 uvY Ym-k+1 uvw, mit j, k und m wie oben. Statt die "Y Y* w"Alternative gleich zu nehmen, kann man die "Y Y* vY"-Alternative iterieren.
Also gilt auch S Y* uviw.
Ê
Beispielsweise ist {anbm | n, m $ 0} regulär, {anbn | n $ 0} hingegen nicht.
Die Pumping-Lemma-Eigenschaft ist nicht hinreichend. Es gibt Sprachen mit diesen Eigenschaften, die aber nicht regulär sind.
75
Das Pumping-Lemma für reguläre Sprachen nützt nur beim Beweisen, dass eine vorgelegte
Sprache L nicht regulär ist. Um aber die Frage beantworten zu können, ob die Sprache L regulär
ist, kann man ggf. folgende Beziehungen verwenden:
Satz:
Sei Σ ein Alphabet und L, L1, L2 f Σ* seien reguläre Sprachen. Dann sind die folgenden
Sprachen auch regulär: L1 c L2 (Vereinigung), L1 \ L2 (Differenz), Σ* \ L (Komplement), L1 1
L2 (Durchschnitt), L1 B L2 (Konkatenation), L*, LR (Spiegelsprache).
Beweis:
76
Bei der Einführung des Grammatikbegriffs wurde bereits das Wortproblem erwähnt. Es ist die
Frage nach der Existenz eines Algorithmus, der bei der Vorlage einer Zeichenkette w und einer
Grammatik G entscheiden kann, ob w 0 L(G) ist. Bei regulären Sprachen ist das Problem:
„Gegeben eine reguläre Sprache L f Σ* und w 0 Σ*. Ist w 0 L?”
stets mit „ja” oder mit „nein” zu entscheiden. (L sei mittels einer der drei Möglichkeiten zur
Charakterisierung regulärer Sprachen definiert.)
Gleiches gilt für das
- Leerheitsproblem: ob der Automat für L überhaupt ein Wort akzeptiert / die Grammatik
für L ein Wort generiert
- Endlichkeitsproblem: ob der Automat für L nur endlich viele Wörter akzeptiert / die
Grammatik für L nur endlich viele Wörter generiert
- Durchschnittsproblem: ob die jeweiligen Automaten für zwei reguläre Sprachen
mindestens ein gemeinsames Wort erkennen
- Äquivalenzproblem: ob zwei Automaten die gleiche Sprache erkennen.
77
9
Wie kann man das Wortproblem bei kontextfreien
Sprachen lösen?
Zur Erinnerung: Erstens, das Wortproblem ist folgende Fragestellung: „Gegeben eine Zeichenkette w 0 G* über einem Alphabet G und eine Grammatik G. Frage: Ist w 0 L(G)?”. Zweitens,
kontextfreie Grammatiken G = (V, G, P, S) sind solche, bei denen die Produktionen die Gestalt
A 6 σ haben, wobei A 0 V und σ 0 (V c G)* ist.
Bei regulären Sprachen ist die Sachlage bzgl. des Wortproblems relativ einfach: Liegt eine
Sprache L(G) in Form ihrer regulären Grammatik vor, konstruiert man den äquivalenten DEA
A zu G und schaut, ob w von A akzeptiert wird. Immer gibt es eine ja/nein-Entscheidung.
Kontextfreie Sprachen wie die für korrekt geklammerte Ausdrücke spielen neben den regulären eine zentrale Rolle bei der Definition von Programmiersprachen. Hier tritt das Wortproblem
in anschaulicher Form z.B. stets bei der Übersetzung von Programmen durch einen Compiler auf
und wird Parsing genannt, das in drei Phasen aufgeteilt wird, in die lexikalische, die syntaktische und die semantische Analyse. HTML-Text gehorcht z.B. einer kontextfreien Grammatik.
Es wurde bereits erwähnt, dass eine geeignete Darstellung für Wörter, die von einer kontextfreien Grammatik erzeugt werden, die Baumstruktur ist. Das Wortproblem für kontextfreie
Grammatiken könnte im Kern auch so gestellt werden: Suche den Parsebaum zu w relativ zu G.
Betrachten wir eine naheliegende Methode zur Erstellung des Syntaxbaumes. Prinzip: Vom
Startsymbol ausgehend werden die Nonterminale „horizontal” expandiert und verglichen, ob das
Erzeugte noch mit der Eingabe kompatibel ist (z. B. dadurch, dass man die übereinstimmenden
Terminale aus Eingabe und Erzeugtem gegeneinander „weg kürzt”). Die „Restwörter” werden
bei Expansion nach unten bzw. oben weitergegeben.
Beispiel:
(1) S 6 aSbS
(2) S 6 aS
(3) S 6 c
78
79
Das gezeigte graphische Verfahren ist sehr intuitiv und wenig geeignet um es zu programmieren. Wir verwenden für eine potenzielle Implementierung einen Kellerungsmechanismus, der in
zwei Ausprägungen vorhanden ist, einen um die Restzeichenkette zu verwalten und einen, der
als „Buchführungskeller” die „Backup”- oder „Sackgassen”-Verwaltung realisiert.
(1) S 6 aSbS
(2) S 6 aS
(3) S 6 c
Eingabe
Satzformkeller
BuchführKeller
Test E/K
Aktion
aacbc
aacbc
acbc
acbc
cbc
cbc
cbc
cbc
cbc
cbc
bc
c
c
c
c
c
c
g
c
c
bc
cbc
cbc
acbc
acbc
acbc
cbc
cbc
cbc
cbc
cbc
cbc
bc
c
c
c
c
c
c
g
S
aSbS
SbS
aSbSbS
SbSbS
aSbSbSbS
SbSbS
aSbSbS
SbSbS
cbSbS
bSbS
SbS
aSbSbS
SbS
aSbS
SbS
cbS
bS
cbS
SbS
bSbS
cbSbS
SbSbS
aSbSbS
SbS
aSbS
SbS
aSbSbS
SbS
aSbS
SbS
cbS
bS
S
aSbS
S
aS
S
c
g
g
1
1a
1a1
1a1a
1a1a1
1a1a
1a1a2
1a1a
1a1a3
1a1a3c
1a1a3cb
1a1a3cb1
1a1a3cb
1a1a3cb2
1a1a3cb
1a1a3cb3
1a1a3cb3c
1a1a3cb3
1a1a3cb
1a1a3c
1a1a3
1a1a
1a1
1a
1a2
1a2a
1a2a1
1a2a
1a2a2
1a2a
1a2a3
1a2a3c
1a2a3cb
1a2a3cb1
1a2a3cb
1a2a3cb2
1a2a3cb
1a2a3cb3
1a2a3cb3c
a…S
a=a
a…S
a=a
c…S
c…a
c…S
c…a
c…S
c=c
b=b
c…S
c…a
c…S
c…a
c…S
c=c
ε…b
k. weit. Prod.
c…S
expandiere mit 1
lösche und merke
expandiere mit 1
lösche und merke
expandiere mit 1
rückgängig machen
expandiere mit 2
rückgängig machen
expandiere mit 3
lösche und merke
lösche und merke
expandiere
rückgängig machen
expandiere
rückgängig machen
expandiere
lösche und merke
restauriere
Y backup
restauriere
k. weit. Prod.
Y backup
restauriere
nächste Prod.
a…S
a=a
c…S
c…a
c…S
c…a
c…S
c=c
b=b
c…S
c…a
c…S
c…a
c…S
c=c
g=g
expandiere mit 2
lösche und merke
expandiere mit 1
rückgängig machen
expandiere mit 2
rückgängig machen
expandiere mit 3
lösche und merke
lösche und merke
expandiere mit 1
rückgängig machen
expandiere mit 2
rückgängig machen
expandiere mit 3
lösche und merke
accept
Ê
80
Bemerkungen:
>
Man beachte im Beispiel, dass Breitensuche durchgeführt wird. Reine Tiefensuche macht
Probleme bei linksrekursiven Symbolen.
>
Werden beim Eingabe/Keller-Test Terminale verglichen, wird bei Gleichheit die Richtigkeit der letzten Produktion angenommen, aber prophylaktisch die Eingabe gespeichert
(könnte auch durch Merker für die Eingabe-Position realisiert werden).
>
Bei Eingabe/Keller-Test auf Nonterminale wird mit der „nächsten” Produktion expandiert. Gibt es keine mehr, wird der aktuelle Expansions-Versuch abgebrochen. Damit ist
aber die vorhergehende Expansion auch eine Sackgasse und die nächste Möglichkeit ist
zu testen.
>
Die Erstellung des Syntaxbaumes nach dieser Methode geschieht von links nach rechts
und liefert die linkskanonische Ableitung (leftmost derivation). Den Vorgang könnte man
wie folgt visualisieren.
81
>
Das Verfahren („systematisches Ausprobieren”) ist intuitiv und deshalb einfach und
verständlich, aber sehr aufwändig. Es gibt zwar bessere Verfahren (etwa von EARLEY
oder von COCKE & KASAMI & YOUNGER), die das Wortproblem hinsichtlich beliebiger kontextfreier Grammatiken zu lösen gestatten; sie sind aber trotzdem für die Praxis
wegen eines immer noch hohen Speicherplatz- und Laufzeitbedarfs als ungeeignet zu betrachten. In der Compilertechnik werden deshalb nur solche Verfahren eingesetzt, die
das Wortproblem in linearer Zeit zu lösen gestatten. Das ist aber nur möglich, wenn man
weitere Einschränkungen hinsichtlich der rechten Seite der Produktionen der kontextfreien Grammatiken macht. Dies führt zu den LL(k)- bzw. LR(k)-Grammatiken.
82
10 Wie kann man mit kontextfreien Grammatiken bequemer arbeiten? (Normalformen)
Bereits bei den regulären Grammatiken konnten wir zeigen, dass man eine linkslineare in eine
äquivalente rechtslineare umformen kann. Für den Umgang mit kontextfreien Grammatiken
kann es insbesondere bei der praktischen Verwendung von Bedeutung sein, dass sie gewisse
Eigenschaften, also Normalformen, erfüllen.
Weil reguläre Grammatiken nur Spezialfälle von kontextfreien sind, gelten die im Folgenden
für kontextfreie Grammatiken dargestellten Verfahren auch für die regulären.
Entfernen nutzloser Terminalsymbole
Es können bei der Angabe der kontextfreien Grammatik G = (V, G, P, S) in der Tupelschreibweise in G mehr Elemente aufgeführt sein, als auf den rechten Seiten von P tatsächlich auftreten.
Deren Eliminierung ist das einfachste Problem, indem aus G alle Symbole entfernt werden, die
nicht auf einer rechten Seite einer Produktion auftreten. So lässt sich zu G eine äquivalente
kontextfreie terminalsymbolreduzierte Grammatik G' = (V, G', P, S) angeben
Entfernen nutzloser Nichtterminalsymbole
Sei G = (V, G, P, S) eine kontextfreie Grammatik. G heißt nonterminalreduziert, wenn gilt
1>
Jedes Nichtterminalsymbol X kann in Teminalsymbole abgeleitet werden, also
X Y* τ, mit τ 0 G* für alle X 0 V
2>
V enthält keine Symbole, die nicht in einer Satzform von G auftreten, also gilt
S Y* σYτ für alle Y 0 V mit σ, τ 0 (V c G)*.
Ist eine Grammatik terminal- und nonterminalreduziert, nennt man sie reduziert.
83
Behauptung:
Zu jeder kontextfreien Grammatik G = (V, G, P, S) lässt sich eine äquivalente kontextfreie
reduzierte Grammatik G''' = (V''', G''', P''', S) konstruieren.
Beweis:
Zunächst wird zur Grammatik G eine äquivalenten Grammatik G' = (V', G, P', S) ohne
nichtterminalisierbare Nonterminale konstruiert.
Dazu wird zunächst die Menge der Nichtterminalsymbole N1 = {X 0 V | X 6 τ, mit τ 0 G*}
gebildet, also es werden alle Nichtterminale gesammelt, die in einem Schritt terminalisiert
werden können. Im nächsten Schritt werden all diejenigen Nichtterminale in die Menge N2 = {X
0 V | X 6 τ mit τ 0 (G c N1)*} aufgenommen, also diejenigen Nichtterminale, die auf der
rechten Seite nur Terminalsymbole und Nichtterminale aus N1 haben. So bildet man schrittweise
Ni+1 = {X 0 V | X Y τ mit τ 0 (G c Ni)*}. Kommt in einem Schritt kein neues Nichtterminal
hinzu, ist man fertig. Dann ist V' = Ni+1 und aus P kann man alle Produktionen entfernen, auf
deren rechter Seite ein nichtterminalisierbares Nichtterminal steht, also P' = P \ {X 6 τ | X ó V'}.
Dann werden alle Nichtterminale gesucht und schließlich aus V' entfernt, die nicht in einer
Satzform auftreten, also aus S ableitbar sind.
Dazu wird zunächst die Menge M1 = {S} gebildet. Im nächsten Schritt werden in der Menge
M2 zusätzlich alle Nichtterminale aufgenommen, die auf der rechten Seite der Produktionen von
S stehen, also M2 = M1 c {X 0 V' | S 6 σXτ mit σ, τ 0 (V' c G)*}. Allgemein: Mi+1 = Mi c {X
0 V' | Y 6 σXτ mit σ, τ 0 (V' c G)*, Y 0 Mi}. Kommt in einem Schritt kein neues Nichtterminal
hinzu, ist man fertig. Dann ist V'' = Mi+1 und P'' = P' \ {X 6 τ | X ó V''}
Im letzten Schritt werden die Terminalsymbole aus G entfernt, die nicht auf einer rechten Seite
einer Produktion aus P'' auftreten. So erhält man G''' und schließlich G''' = (V''' = V'', G''', P''' =
P'', S).
Dass L(G) = L(G''') ist, folgt aus der Konstruktion.
Ê
84
Eliminieren von g-Regeln
Bereits bei der Einführung in die Chomsky-Hierarchie wurde wegen der Forderung nach
Monotonie bei den Typ1-Grammatiken auf die Problematik mit g-Regeln hingewiesen, für die
man spezielle Annahmen machen muss, um nicht die Hierarchie zu zerstören. Es wird sich
zeigen, dass man bei kontextfreien Grammatiken durchaus ohne diesen Regeltyp auskommt,
wenn man ausschließlich die Regel S 6 g verwendet, falls das leere Wort Element der Sprache
sein soll.
Behauptung:
Zu jeder kontextfreien Grammatik G = (V, G, P, S) mit g ó L(G) lässt sich eine äquivalente
kontextfreie Grammatik G' = (V, G, P', S) angeben ohne Regeln der Form X 6 g und X 0 V.
Beweis:
Zunächst wird die Menge der Nichtterminalsymbole N1 = {X 0 V | X 6 g} bestimmt, also es
werden alle Nichtterminale gesammelt, die in einem Schritt ins leere Wort abgeleitet werden
können. Im nächsten Schritt werden all diejenigen Nichtterminale in die Menge N2 = {X 0 V |
X 6 τ mit τ 0 N1*} aufgenommen, also diejenigen Nichtterminale, die auf der rechten Seite nur
Nichtterminale aus N1 haben. So bildet man schrittweise Ni+1 = {X 0 V | X 6 τ mit τ 0 Ni*}.
Kommt in einem Schritt kein neues Nichtterminal hinzu, ist man fertig.
Im nächsten Schritt fügt man für alle Regeln mit einem X 0 Ni+1 auf der rechten Seite eine
Regel ohne dieses X hinzu, weil ja dieses X nicht mehr nach g abgeleitet werden kann. Also für
eine Regel Y 6 σXτ 0 P mit σ, τ 0 (VcG)* und |στ| > 0 kommt die Regel Y 6 στ nach P'.
Dann werden alle Regeln Z 6 g aus P entfernt.
Dass L(G) = L(G') ist, folgt aus der Konstruktion.
Ê
Soll g 0 L(G) gelten, nimmt man einfach die Regel S 6 g hinzu, falls S nicht auf einer rechten
Seite einer Produktion auftaucht. Falls dies der Fall ist, muss ein neues Startsymbol S' eingeführt
werden und die Regel S' 6 g, außerdem für jede Regel S 6 τ die Regel S' 6 τ.
Beispiel:
Ê
85
Eliminieren von Kettenregeln
Kettenregeln sind von der Art A 6 B mit A, B 0 V.
Behauptung:
Zu jeder reduzierten kontextfreien Grammatik G = (V, G, P, S) gibt es eine äquivalente
reduzierte kontextfreie Grammatik G' ohne Kettenregeln.
Beweis:
Um die Kettenregeln zu entfernen, muss man folgendermaßen vorgehen:
Suche die Zyklen der Art B1 6 B2 6 ... Bk 6 B1. Ersetze in den Produktionen jedes Bi mit 1 #
i # k durch ein neues Nichtterminal B und entferne die sich ergebende Regel B 6 B. Außerdem
entferne die Bi mit 1 # i # k aus V. (Die so erhaltene Grammatik ist äquivalent zur alten.)
Lege eine Nummerierung der Nichtterminale, die in den verbliebenen (zyklenfreien) Kettenregeln noch stehen, so fest, dass i < j gilt, wenn Ai 6 Aj. Dann ersetze - beim höchsten Index
beginnend und fortlaufend bis 1 - quasi „rückwärts” jede Regel Aj 6 τ mit τ 0 (V c G)* durch
Ai 6 τ und streiche die Regel Ai 6 Aj.
Dass L(G) = L(G') ist, folgt aus der Konstruktion.
Ê
Die Beibehaltung der Reihenfolge ist wesentlich. Betrachte die Grammatik mit den Regeln
S6A
A6B
B6b
Dies legt die Reihenfolge S, A, B fest. Nach Vorschrift ersetzt man A 6 B durch A 6 b und S 6
A durch S 6 b.
Hält man sich nicht an die Reihenfolge der „Rückwärtssubstitution” und würde man z.B. erst
S 6 A eliminieren, erhielte man wieder eine Kettenregel S 6 B.
Beispiel:
Ê
86
Chomsky-Normalform
Für kontextfreie Grammatiken gibt es ein Normalformtheorem von Chomsky. Die ChomskyNormalform braucht man u.a. zum bereits erwähnten Syntaxanalyseverfahren von Cocke &
Kasami & Younger.
Behauptung:
Eine reduzierte kontextfreie Grammatik G = (V, G, P, S) mit g ó L(G) und die frei von
Kettenregeln ist lässt sich so zu einer äquivalenten reduzierten Grammatik G' = (V', G, P', S)
umformen, dass die Produktionen von G' auf ihren rechten Seiten entweder genau zwei Nichtterminale oder nur ein Terminalsymbol haben, also P f V × (VV c G) ist.
Beweis(idee):
Die Vorgehensweise ist nicht schwer einzusehen:
Man führt zunächst für jedes Terminalsymbol a ein neues Nichtterminal, z.B. [a], ein und fügt
zu den Produktionen P' der zu konstruierenden Grammatik die Produktionen [a] 6 a hinzu sowie
[a] zu V'. Außerdem ändert man die Produktionen mit Y 6 σaτ zu Y 6 σ[a]τ
Alle Produktionen, die auf der rechten Seite mehr als zwei Nichtterminale haben, wie z.B. A
6 BCDEF, werden sukzessive umgeformt zu A 6 B[CDEF] und [CDEF] 6 D[EF] und [EF] 6
EF. Die so entstandenen Produktionen bzw. Nichtterminale werden in P' bzw. V' aufgenommen.
Dass L(G) = L(G') ist, folgt aus der Konstruktion.
Ê
Beispiel:
87
Greibach-Normalform
Eine kontextfreie Grammatik G = (V, G, P, S) ist in der Greibach-Normalform, wenn die
Produktionen Elemente aus V × (G B V*) sind.
Die Gestalt der Produktionen hat also einen Charakter vergleichbar mit der Rechtslinearität bei
den regulären Sprachen.
Behauptung (ohne Beweis):
Zu jeder kontextfreien Grammatik G = (V, G, P, S) mit g ó L(G) gibt es eine äquivalente
kontextfreie Grammatik in der Greibach-Normalform.
Ê
Diese Konstruktion kann in dem Sinne verschärft werden, dass die Produktionen nur Elemente
aus V × G oder aus V × (G B V) oder aus V × (G B V B V) sind, was den Charakter der „Rechtslinearität” noch verstärkt oder anders ausgedrückt, dass die Greibach-Normalform eine Verallgemeinerung der rechtslinearen Grammatiken ist.
Die Umformung in die Greibach-Normalform ist recht umständlich und aus einfachen Grammatiken können äquivalente Monstergrammatiken mit vielen Regeln werden.
88
Document
Kategorie
Seele and Geist
Seitenansichten
11
Dateigröße
612 KB
Tags
1/--Seiten
melden