close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

10 Wie kann man mit kontextfreien Grammatiken be- quemer

EinbettenHerunterladen
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. (Zur Erinnerung: Eine weitere Forderung war, dass das Startsymbol S nicht auf der
rechten Seite einer Produktion auftauchen darf.)
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], [CDEF] 6 C[DEF], [DEF]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
Gesundheitswesen
Seitenansichten
11
Dateigröße
135 KB
Tags
1/--Seiten
melden