Normalform von Greibach
In der theoretischen Informatik und insbesondere in der formalen Sprachtheorie liegt eine algebraische Grammatik in Greibach-Normalform (in Englisch, Greibach-Normalform oder GNF ) vor, wenn die richtigen Mitglieder ihrer Regeln alle mit einem Terminalsymbol beginnen , möglicherweise gefolgt von einem oder mehreren Variablen . Eine Variante ermöglicht es einer zusätzlichen Regel, das leere Wort zu generieren, wenn es Teil der Sprache ist. Diese normale Form ist nach Sheila Greibach benannt , die sie eingeführt und ihre Existenz bewiesen hat.
Es gibt andere normale Formen der Grammatik, wie Chomskys Normalform oder Grammatiken ohne linke Rekursion . Greibachs Normalform ist die aufwändigste dieser Normalformen und wurde weiter verfeinert.
Beschreibung
Eine algebraische Grammatik liegt in Greibach-Normalform vor, wenn alle Regeln die Form haben:
BEIM→beimBEIM1BEIM2⋯BEIMnicht{\ displaystyle A \ bis aA_ {1} A_ {2} \ cdots A_ {n}}oder
S.→ε{\ displaystyle S \ to \ varepsilon}wo ist eine Variable , ist ein Buchstabe und
ist eine möglicherweise leere Folge von Variablen; ist das Axiom und ε ist das leere Wort .
BEIM{\ displaystyle A}beim{\ displaystyle a}BEIM1BEIM2...BEIMnicht{\ displaystyle A_ {1} A_ {2} \ ldots A_ {n}}S.{\ displaystyle S}
Eine Grammatik in normaler Greibach-Form ist insbesondere ohne Linksrekursion . Die Haupteigenschaft ist, dass jede algebraische Grammatik in eine äquivalente Grammatik in normaler Form von Greibach umgewandelt werden kann, ein Satz, der 1965 von Sheila Greibach aufgestellt wurde.
Es gibt mehrere Konstruktionen. Wenn es keine Epsilon-Regel gibt , ist der Algorithmus einfacher; Es gibt Zeitkomplexitätstransformationen im allgemeinen Fall und Zeitkomplexität, wenn die Grammatik keine Einheitsregel (der Form für eine Variable ) hat.
S.→ε{\ displaystyle S \ to \ varepsilon}Ö((nicht4){\ displaystyle O (n ^ {4})}Ö((nicht3){\ displaystyle O (n ^ {3})}BEIM→B.{\ displaystyle A \ to B}B.{\ displaystyle B}
In der normalen Greibach-Form erzeugt eine Ableitung bei jedem Ableitungsschritt einen Buchstaben eines bestimmten Sprachworts: Die Länge der Ableitung ist daher gleich der Länge des Wortes. Die normale Form kann in äquivalenter Weise verwendet werden, um einen Druckknopfautomaten zu konstruieren , der die Wörter der Sprache in Echtzeit akzeptiert, dh bei jedem Berechnungsschritt einen Buchstaben des eingegebenen Wortes liest.
Konstruktion
Die Konstruktion einer Grammatik in normaler Form von Greibach aus einer algebraischen Grammatik, die von einem Teil der Fächer gegeben wird, die in vielen theoretischen Computerlehrbüchern über formale Sprachen, Automaten und deren Komplexität behandelt werden. Eine der Konstruktionen besteht aus mehreren Phasen:
Vorphase: Aufhebung der Epsilon-Regeln
Wir können davon ausgehen, dass das Axiom der Grammatik nicht in einem rechten Glied einer Regel vorkommt.
Eine Regel , bei der das Axiom nicht ist, wird gelöscht. Wir betrachten jede Regel , wo erscheint in , und wir fügen, bei jedem Auftreten , die Regel der Grammatik, es sei denn wir eine epsilon-Regel erstellen. Zum Beispiel wenn
BEIM→ε{\ displaystyle A \ to \ varepsilon}BEIM{\ displaystyle A}B.→α{\ displaystyle B \ to \ alpha}BEIM{\ displaystyle A}α{\ displaystyle \ alpha}α=βBEIMγ{\ displaystyle \ alpha = \ beta A \ gamma}B.→βγ{\ displaystyle B \ to \ beta \ gamma}
B.→beimBEIMbBEIMvs.{\ displaystyle B \ to aAbAc}Wir fügen die drei Regeln hinzu
B.→beimbBEIMvs.,B.→beimBEIMbvs.,B.→beimbvs.{\ displaystyle B \ zu abAc, B \ zu aAbc, B \ zu abc}.
Eine Regel, deren rechtes Element Variablen enthält , die alle aus dem leeren Wort stammen, kann somit neue Regeln aufgeben .
nicht{\ displaystyle n}2nicht{\ displaystyle 2 ^ {n}}
Zweite Phase: Aufhebung der Einheitsregeln
Eine Einheitsregel ist eine Regel der Form , wobei es sich um eine Variable handelt. Um diese Art von Regel zu beseitigen, ersetzen wir eine solche Regel durch die Regel
BEIM→B.{\ displaystyle A \ to B}B.{\ displaystyle B}
BEIM→α{\ displaystyle A \ to \ alpha}für jede Regel
B.→α{\ displaystyle B \ to \ alpha}(es sei denn, es handelt sich um eine zuvor entfernte Einheitsregel). Diese Technik wird bei Zyklen (wie dem Vorhandensein von drei Regeln ) durch die Identifizierung der Variablen eines Zyklus vervollständigt : Sie werden alle durch eine von ihnen ersetzt.
BEIM→B.,B.→VS,VS→BEIM{\ Anzeigestil A \ bis B, B \ bis C, C \ bis A}
Formatierung normal
Wir nehmen die Grammatik ohne ε-Regeln und ohne Einheitsregeln an. Wir nehmen die in nummerierten Variablen an ; Wir definieren eine Folge von Grammatiken, wobei es sich um die anfängliche Grammatik handelt, mit der Eigenschaft, dass die Variablen in nicht am Kopf der rechten Regelelemente angezeigt werden. Wir gehen davon aus, dass die Grammatik konstruiert ist, und gehen in zwei Schritten vor
BEIM1,BEIM2,...,BEIMm{\ displaystyle A_ {1}, A_ {2}, \ dots, A_ {m}}G0,G1,...,Gnicht{\ displaystyle G_ {0}, G_ {1}, \ dots, G_ {n}}G0{\ displaystyle G_ {0}}Gich{\ displaystyle G_ {i}}BEIM1,...,BEIMich{\ displaystyle A_ {1}, \ ldots, A_ {i}}Gich- -1{\ displaystyle G_ {i-1}}
1. Entfernen der linken Rekursion fürBEIMich{\ displaystyle A_ {i}} : Wir entfernen die Überschriften der Regeln von : den Regeln
BEIMich{\ displaystyle A_ {i}}BEIMich{\ displaystyle A_ {i}}
BEIMich→BEIMichα1∣...∣BEIMichαnicht∣β1∣...∣βm{\ displaystyle A_ {i} \ rightarrow A_ {i} \ alpha _ {1} \ mid \ ldots \ mid A_ {i} \ alpha _ {n} \ mid \ beta _ {1} \ mid \ ldots \ mid \ Beta _ {m}}wo die nicht anfangen mit ersetzt werden durch
βj{\ displaystyle \ beta _ {j}}BEIM{\ displaystyle A}
BEIMich→β1BEIMich'∣...∣βmBEIMich'∣β1∣...∣βm{\ displaystyle A_ {i} \ rightarrow \ beta _ {1} A '_ {i} \ mid \ ldots \ mid \ beta _ {m} A' _ {i} \ mid \ beta _ {1} \ mid \ ldots \ mid \ beta _ {m}}
BEIMich'→α1BEIMich'∣...∣αnichtBEIMich'∣α1∣...∣αnicht{\ displaystyle A '_ {i} \ rightarrow \ alpha _ {1} A' _ {i} \ mid \ ldots \ mid \ alpha _ {n} A '_ {i} \ mid \ alpha _ {1} \ mid \ ldots \ mid \ alpha _ {n}}
2. Entfernen von Vorkommen des KopfesBEIMich{\ displaystyle A_ {i}} : Das Vorkommen von Variablen, die in den rechten Regelelementen am Kopf erscheinen oder erscheinen können, wird durch den Regelsatz dieser Variablen ersetzt.
BEIMj((1≤j≤ich){\ displaystyle A_ {j} (1 \ leq j \ leq i)}
Wenn am Ende in den rechten Elementen anderer Regeln als am Kopf noch Endbuchstaben vorhanden sind, werden diese durch eine zusätzliche Variable , eine für jeden Buchstaben , mit der Regel ersetzt .
T.beim{\ displaystyle T_ {a}}beim{\ displaystyle a}T.beim→beim{\ displaystyle T_ {a} \ to a}
Beispiel
Hier ist ein Beispiel aus Olivier Cartons Buch (wir schreiben statt ):
BEIM,B.,VS{\ displaystyle A, B, C}BEIM1,BEIM2,BEIM3{\ displaystyle A_ {1}, A_ {2}, A_ {3}}
Grammatik G 0 :
BEIM→BEIMB.∣beim{\ displaystyle A \ bis AB \ mid a}
B.→B.VS∣b{\ displaystyle B \ bis BC \ mid b}
VS→VSBEIM∣vs.{\ displaystyle C \ to CA \ mid c}
Die beiden Regeln von werden ersetzt durch
BEIM{\ displaystyle A}
BEIM→beimBEIM'∣beim,BEIM'→B.BEIM'∣B.{\ displaystyle A \ bis aA '\ mid a, \ quad A' \ bis BA '\ mid B}.
Wir erhalten :
Grammatik G 1 :
BEIM→beimBEIM'∣beim{\ displaystyle A \ to aA '\ mid a}
BEIM'→B.BEIM'∣B.{\ displaystyle A '\ to BA' \ mid B}
B.→B.VS∣b{\ displaystyle B \ bis BC \ mid b}
VS→VSBEIM∣vs.{\ displaystyle C \ to CA \ mid c}
Die beiden Regeln von werden ersetzt durch
B.{\ displaystyle B}
B.→bB.'∣b,B.'→VSB.'∣VS{\ displaystyle B \ bis bB '\ mid b, \ quad B' \ bis CB '\ mid C}und die Vorkommen oben auf
B.{\ displaystyle B}
werden durch diese beiden Regeln ersetzt. Wir erhalten :
Grammatik G 2 :
BEIM→beimBEIM'∣beim{\ displaystyle A \ to aA '\ mid a}
BEIM'→bB.'BEIM'∣bBEIM'∣bB.'∣b{\ displaystyle A '\ to bB'A' \ mid bA '\ mid bB' \ mid b}
B.→bB.'∣b{\ displaystyle B \ to bB '\ mid b}
B.'→VSB.'∣VS{\ displaystyle B '\ to CB' \ mid C}
VS→VSBEIM∣vs.{\ displaystyle C \ to CA \ mid c}
Ebenso werden die beiden Regeln von in einem ersten Schritt durch ersetzt
VS{\ displaystyle C}
VS→vs.VS'∣vs.,VS'→BEIMVS'∣BEIM{\ displaystyle C \ bis cC '\ mid c, \ quad C' \ bis AC '\ mid A},
Die führende Variable wird jedoch ebenso wie die führende Variable durch ihre Regeln ersetzt . Wir bekommen die Grammatik:
BEIM{\ displaystyle A}VS{\ displaystyle C}
Grammatik G 3
BEIM→beimBEIM'∣beim{\ displaystyle A \ to aA '\ mid a}
BEIM'→bB.'BEIM'∣bBEIM'∣bB.'∣b{\ displaystyle A '\ to bB'A' \ mid bA '\ mid bB' \ mid b}
B.→bB.'∣b{\ displaystyle B \ to bB '\ mid b}
B.'→vs.VS'B.'∣vs.B.'∣vs.VS'∣vs.{\ displaystyle B '\ bis cC'B' \ mid cB '\ mid cC' \ mid c}
VS→vs.VS'∣vs.{\ displaystyle C \ to cC '\ mid c}
VS'→beimBEIM'VS'∣beimVS'∣beimBEIM'∣beim{\ displaystyle C '\ to aA'C' \ mid aC '\ mid aA' \ mid a}
Andere normale Formen
Quadratische Normalform
Eine Grammatik liegt in Greibachs quadratischer Normalform vor , wenn alle Regeln der Form entsprechen
BEIM→beimV.{\ displaystyle A \ to aV}wobei sich aus höchstens zwei Variablen zusammensetzt, wenn also zusätzlich die richtigen Regelelemente höchstens 3 lang sind. Die obige Grammatik und die Grammatik:
V.{\ displaystyle V}
S.→beimS.S.|b{\ displaystyle S \ to aSS | b}Die Lukasiewicz-Sprache ist in quadratischer Form, Grammatik
S.→beimS.S.S.|b{\ displaystyle S \ to aSSS | b}ist nicht. Es kann durch Gruppieren aufeinanderfolgender Vorkommen in eine quadratische Grammatik umgewandelt werden. Hier führen wir eine neue Variable ein und ersetzen die Grammatik durch:
T.{\ displaystyle T}
S.→beimS.T.|b,T.→S.S.{\ displaystyle S \ zu aST | b, \ quad T \ zu SS}Die Grammatik ist nicht mehr in normaler Greibach-Form, aber wie zuvor ersetzen wir die führende Variable in der Regel für , die daher
ergibtT.{\ displaystyle T}T.→beimS.S.S.S.∣bS.{\ displaystyle T \ to aSSSS \ mid bS}
S.→beimS.T.|b,T.→beimT.T.∣bS.{\ displaystyle S \ zu aST | b, \ quad T \ zu aTT \ mid bS}.
Bilaterale Normalform
Eine Grammatik liegt in bilateraler Normalform oder in doppelter normaler Greibach-Form vor, wenn alle Regeln mit einem Endbuchstaben beginnen und enden, formal, wenn sich die richtigen Regelelemente in befinden , wo und sind das terminale und nicht-terminale Alphabet der Grammatik. Eine Grammatik liegt in quadratischer bilateraler Normalform vor, wenn die richtigen Regelelemente vorhanden sind. Wenn also die richtigen Regelelemente eine Länge von 4 oder weniger haben, wurde diese Konstruktion von Günter Hotz eingeführt.
Σ∪ΣV.∗Σ{\ displaystyle \ Sigma \ cup \ Sigma V ^ {*} \ Sigma}Σ{\ displaystyle \ Sigma}V.{\ displaystyle V}Σ∪Σ((ε∪V.∪V.2)Σ{\ displaystyle \ Sigma \ cup \ Sigma (\ varepsilon \ cup V \ cup V ^ {2}) \ Sigma}
Andere Konstruktionen
Eine andere, algebraischere Konstruktion wurde von Daniel J. Rosenkrantz vorgeschlagen. Es basiert auf der Lösung eines Gleichungssystems in der Algebra von Teilen auf einem freien Monoid. Diese Methode führt direkt zu einer quadratischen Grammatik, wenn wir von einer Grammatik in Chomsky-Normalform ausgehen . Andere Konstruktionen und Verallgemeinerungen wurden von verschiedenen Autoren angegeben.
Anmerkungen und Referenzen
-
Hopcroft und Ullman 1979 , p. 95.
-
(in) Sheila A. Greibach , " Ein neuer Normalformsatz für kontextfreie Grammatik-Satzstruktur " , Journal of the ACM , vol. 12, n o 1,Januar 1965, p. 42–52 ( DOI 10.1145 / 321250.321254 ).
-
(in) Norbert Blum und Robert Koch , " Greibach Normal Form Transformation Revisited " , Information & Computation , vol. 150, n o 1,
1999, p. 112–118 ( DOI 10.1006 / inco.1998.2772 , online lesen ).
-
Wir führen für die Konstruktion von Chomskys Normalform eine neue Variable ein, die zum Axiom wird, und eine einzige zusätzliche Regel , bei der es sich um das alte Axiom handelt.S.0{\ displaystyle S_ {0}}S.0→S.{\ displaystyle S_ {0} \ to S}S.{\ displaystyle S}
-
Hopcroft, Motwani und Ullman 2007 , p. 268.
-
Karton 2008 .
-
Günter Hotz, „ Normalformtransformationen kontextfreier Grammatiken “, Acta Cybernetica , vol. 4, n o 1,
1978, p. 65-84.
-
(in) Joost Engelfriet , " Ein elementarer Beweis der dualen Greibach-Normalform " , Information Processing Letters , vol. 44, n o 6,
1992, p. 291–293 ( DOI 10.1016 / 0020-0190 (92) 90101-Z ).
-
Daniel J. Rosenkrantz, „ Matrixgleichungen und Normalformen für kontextfreie Grammatiken “, Journal of the ACM , vol. 14, n o 3,
Juli 1967, p. 501–507.
-
(in) Ryo Yoshinaka , " Ein elementarer Beweis für eine Verallgemeinerung der regulären doppelten Greibach-Form " , Information Processing Letters , vol. 109, n o 10,2009, p. 490–492 ( DOI 10.1016 / j.ipl.2009.01.015 ).
Literaturverzeichnis
Anleitungen
-
Olivier Carton, Formale Sprachen, Berechenbarkeit und Komplexität: Bachelor- und Master-Abschluss in Mathematik oder Informatik, Informatikoption der Aggregation von Mathematik , Paris, Vuibert,2008237 p. ( ISBN 978-2-7117-2077-4 , online lesen ) - Abschnitt 2.5 Normalform Greibach.
- John E. Hopcroft und Jeffrey D. Ullman , Einführung in die Automatentheorie, Sprachen und Berechnungen , Addison-Wesley,1979
- (en) John E. Hopcroft , Rajeev Motwani und Jeffrey D. Ullman , Einführung in die Automatentheorie, Sprachen und Berechnung , Addison-Wesley ,2007, 3 e ed. ( ISBN 978-0-32146225-1 )
-
(en) John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman, Einführung in die Automatentheorie, Sprachen und Berechnung , Pearson Addison Wesley,2007, 3 e ed. xvii + 535 p. ( ISBN 978-0-321-45536-9 und 0-321-45536-3 ) - Seite 277.
-
(de) Peter Linz, Eine Einführung in formale Sprachen und Automaten , Jones & Bartlett Learning,2001410 p. ( ISBN 978-0-7637-1422-2 und 0763714224 , online lesen ).
-
(de) Katrin Erk und Lutz Priese, Theoretische Informatik: eine umfassende Einführung , Berlin, Springer,2008485 p. ( ISBN 978-3-540-76319-2 , OCLC 244015158 ) - 6.8.1 6.3 Chomsky- und Greibach-Normalform p. 121 .
-
(en) Michael A. Harrison, Einführung in die formale Sprachtheorie , Lesen, Messe. ua Addison-Wesley,1978594 p. ( ISBN 0-201-02955-3 , OCLC 266962302 ) - Abschnitt 4.6 Greibach Normalform, p. 111-120 .
Klassen
Siehe auch
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">