Greibach normális formája
Az elméleti számítógép-tudomány és különösen a formális nyelvek elmélete , egy algebrai nyelvtani van Greibach normál formában (angol, Greibach normál forma vagy GNF ), ha a megfelelő tagjainak szabályok minden kezdődik egy terminális szimbólum , esetleg majd egy vagy több változók . Egy változat lehetővé teszi egy további szabály létrehozását az üres szó létrehozására, ha az a nyelv része. Ez a normális forma Sheila Greibachról kapta a nevét, aki bevezette és bebizonyította létezését.
A nyelvtannak más normális formái is léteznek, például Chomsky normális alakja vagy bal rekurzió nélküli nyelvtan . Greibach normális alakja a legkifinomultabb e normális formák közül, és tovább finomították.
Leírás
Az algebrai nyelvtan Greibach normál formában van, ha az összes szabály a következő formájú:
NÁL NÉL→nál nélNÁL NÉL1NÁL NÉL2⋯NÁL NÉLnem{\ displaystyle A \ to aA_ {1} A_ {2} \ cdots A_ {n}}vagy
S→ε{\ displaystyle S \ to \ varepsilon}ahol egy változó , egy betű és
egy lehetséges üres változósor; az axióma és az ε az üres szó .
NÁL NÉL{\ displaystyle A}nál nél{\ displaystyle a}NÁL NÉL1NÁL NÉL2...NÁL NÉLnem{\ displaystyle A_ {1} A_ {2} \ ldots A_ {n}}S{\ displaystyle S}
A grammatika normál Greibach formában kifejezetten bal rekurzió nélkül történik . A fő tulajdonság az, hogy bármely algebrai nyelvtan átalakítható Greibach normál alakjában ekvivalens nyelvtanná, amely tétel 1965-ben jött létre Sheila Greibach által.
Számos konstrukció létezik. Ha nincs epsilon-szabály , az algoritmus egyszerűbb; vannak időbeli összetettség-transzformációk általános esetben és az idő- összetettség, ha a nyelvtannak nincs egységességi szabálya ( a változó alakja ).
S→ε{\ displaystyle S \ to \ varepsilon}O(nem4){\ displaystyle O (n ^ {4})}O(nem3){\ displaystyle O (n ^ {3})}NÁL NÉL→B{\ displaystyle A \ to B}B{\ displaystyle B}
Normál Greibach alakban egy levezetés minden levezetési lépésben egy adott nyelvű szó betűjét generálja: a levezetés hossza tehát megegyezik a szó hosszával. A normál formát ekvivalens módon lehet használni egy nyomógombos automata felépítéséhez, amely valós időben fogadja el a nyelv szavait, vagyis amely minden számítási lépésben beolvassa a beviteli szó betűjét.
Építkezés
A Greibach normál formájú nyelvtanának felépítése algebrai nyelvtanból, amelyet számos elméleti számítógépes tankönyvben kezelt tantárgyak egy része adott formális nyelvekre, automatákra és azok összetettségére. Az egyik konstrukció több fázisból áll:
Előzetes szakasz: az epsilon-szabályok eltávolítása
Feltételezhetjük, hogy a nyelvtan axióma nem jelenik meg egy szabály jobb tagjában.
Egy szabály , ahol az axióma nincs, el van nyomva; figyelembe vesszük az egyes szabályokat, ahol megjelenik , és minden előforduláshoz hozzáadjuk a szabályt a nyelvtanhoz, hacsak nem hozunk létre epsilon-szabályt. Például, ha
NÁL NÉL→ε{\ displaystyle A \ to \ varepsilon}NÁL NÉL{\ displaystyle A}B→α{\ displaystyle B \ to \ alpha}NÁL NÉL{\ displaystyle A}α{\ displaystyle \ alpha}α=βNÁL NÉLγ{\ displaystyle \ alpha = \ beta A \ gamma}B→βγ{\ displaystyle B \ to \ beta \ gamma}
B→nál nélNÁL NÉLbNÁL NÉLvs.{\ displaystyle B \ to aAbAc}hozzáadjuk a három szabályt
B→nál nélbNÁL NÉLvs.,B→nál nélNÁL NÉLbvs.,B→nál nélbvs.{\ displaystyle B \ abAc, B \ aAbc, B \ abc}.
Az a szabály, amelynek jobb tagja olyan változókat tartalmaz, amelyek mind az üres szóból származnak, feladhatja az új szabályokat.
nem{\ displaystyle n}2nem{\ displaystyle 2 ^ {n}}
Második szakasz: az egységszabályok eltávolítása
Az egységszabály a forma szabálya , ahol egy változó. Az ilyen típusú szabályok kiküszöbölése érdekében egy ilyen szabályt felváltunk a szabályra
NÁL NÉL→B{\ displaystyle A \ to B}B{\ displaystyle B}
NÁL NÉL→α{\ displaystyle A \ to \ alpha}minden szabályhoz
B→α{\ displaystyle B \ to \ alpha}(hacsak nem egy korábban eltávolított egységszabályról van szó). Ezt a technikát a ciklusok (például három szabály megléte ) esetében a ciklus változóinak azonosításával egészítik ki : mindegyiket helyettesíti az egyik.
NÁL NÉL→B,B→VS,VS→NÁL NÉL{\ displaystyle A \ B, B \ C, C \ A}}
Normál formázás
Feltételezzük a nyelvtant ε-szabályok és egységszabályok nélkül. Feltételezzük a számozott változókat ; meghatározzuk a nyelvtanok sorozatát , ahol a kezdeti nyelvtan, azzal a tulajdonsággal, hogy a változók nem jelennek meg a megfelelő szabálytagok élén. Feltételezzük, hogy a nyelvtan fel van építve, és két szakaszban haladunk
NÁL NÉL1,NÁL NÉL2,...,NÁL NÉLm{\ displaystyle A_ {1}, A_ {2}, \ pontok, A_ {m}}G0,G1,...,Gnem{\ displaystyle G_ {0}, G_ {1}, \ dots, G_ {n}}G0{\ displaystyle G_ {0}}Gén{\ displaystyle G_ {i}}NÁL NÉL1,...,NÁL NÉLén{\ displaystyle A_ {1}, \ ldots, A_ {i}}Gén-1{\ displaystyle G_ {i-1}}
1. eltávolítása a bal rekurzió számáraNÁL NÉLén{\ displaystyle A_ {i}} : eltávolítjuk a fejléceket a szabályok : a szabályok
NÁL NÉLén{\ displaystyle A_ {i}}NÁL NÉLén{\ displaystyle A_ {i}}
NÁL NÉLén→NÁL NÉLénα1∣...∣NÁL NÉLénαnem∣β1∣...∣βm{\ displaystyle A_ {i} \ rightarrow A_ {i} \ alpha _ {1} \ mid \ ldots \ middle A_ {i} \ alpha _ {n} \ mid \ beta _ {1} \ mid \ ldots \ mid \ béta _ {m}}ahol a nem kezdõdnek helyébe a
βj{\ displaystyle \ beta _ {j}}NÁL NÉL{\ displaystyle A}
NÁL NÉLén→β1NÁL NÉLén′∣...∣βmNÁL NÉLén′∣β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}}
NÁL NÉLén′→α1NÁL NÉLén′∣...∣αnemNÁL NÉLén′∣α1∣...∣αnem{\ displaystyle A '_ {i} \ rightarrow \ alpha _ {1} A' _ {i} \ mid \ ldots \ mid \ alpha _ {n} A '_ {i} \ mid \ alpha _ {1} \ mid \ ldots \ mid \ alpha _ {n}}
2. eltávolítása fejNÁL NÉLén{\ displaystyle A_ {i}} események: előfordulásait változók , amelyek jelenik meg vagy jelenik meg a fejét a jó tagjait szabályok helyébe a szabályrendszer ezeket a változókat.
NÁL NÉLj(1≤j≤én){\ displaystyle A_ {j} (1 \ leq j \ leq i)}
Ha a végén a szabályok jobb tagjaiban nem a végén, hanem a végén fejlõdõ betûk maradnak, akkor azokat egy további változó váltja fel , minden betûhöz egyet , a szabállyal .
Tnál nél{\ displaystyle T_ {a}}nál nél{\ displaystyle a}Tnál nél→nál nél{\ displaystyle T_ {a} \ to}
Példa
Íme egy példa Olivier Carton könyvéből (mi helyett írunk ):
NÁL NÉL,B,VS{\ displaystyle A, B, C}NÁL NÉL1,NÁL NÉL2,NÁL NÉL3{\ displaystyle A_ {1}, A_ {2}, A_ {3}}
G 0 nyelvtan :
NÁL NÉL→NÁL NÉLB∣nál nél{\ displaystyle A \ AB-ig \ mid a}
B→BVS∣b{\ displaystyle B \ BC-ig \ b közepe}
VS→VSNÁL NÉL∣vs.{\ displaystyle C \ to CA \ mid c}
A két szabály helyébe a következő lép
NÁL NÉL{\ displaystyle A}
NÁL NÉL→nál nélNÁL NÉL′∣nál nél,NÁL NÉL′→BNÁL NÉL′∣B{\ displaystyle A \ to aA '\ mid a, \ quad A' \ to BA '\ B közepe}.
Azt kapjuk :
G 1 nyelvtan :
NÁL NÉL→nál nélNÁL NÉL′∣nál nél{\ displaystyle A \ to aA '\ mid a}
NÁL NÉL′→BNÁL NÉL′∣B{\ displaystyle A '\ to BA' \ B közepe}
B→BVS∣b{\ displaystyle B \ BC-ig \ b közepe}
VS→VSNÁL NÉL∣vs.{\ displaystyle C \ to CA \ mid c}
A két szabály helyébe a következő lép
B{\ displaystyle B}
B→bB′∣b,B′→VSB′∣VS{\ displaystyle B \ to bB '\ b közepe, \ quad B' \ to CB '\ közepe C}, és az előfordulások a tetején
B{\ displaystyle B}
helyébe ez a két szabály lép. Azt kapjuk :
G 2 nyelvtan :
NÁL NÉL→nál nélNÁL NÉL′∣nál nél{\ displaystyle A \ to aA '\ mid a}
NÁL NÉL′→bB′NÁL NÉL′∣bNÁL NÉL′∣bB′∣b{\ displaystyle A '\ to bB'A' \ mid bA '\ mid bB' \ mid b}
B→bB′∣b{\ displaystyle B \ to bB '\ b közepe}
B′→VSB′∣VS{\ displaystyle B '\ to CB' \ C közepe}
VS→VSNÁL NÉL∣vs.{\ displaystyle C \ to CA \ mid c}
Hasonlóképpen, a két szabály helyébe az első lépés lép
VS{\ displaystyle C}
VS→vs.VS′∣vs.,VS′→NÁL NÉLVS′∣NÁL NÉL{\ displaystyle C \ to cC '\ mid c, \ quad C' \ to AC '\ mid A},
de a vezető változót a szabályai helyettesítik, csakúgy, mint a vezető változót . Megkapjuk a nyelvtant:
NÁL NÉL{\ displaystyle A}VS{\ displaystyle C}
Nyelvtan G 3
NÁL NÉL→nál nélNÁL NÉL′∣nál nél{\ displaystyle A \ to aA '\ mid a}
NÁL NÉL′→bB′NÁL NÉL′∣bNÁL NÉL′∣bB′∣b{\ displaystyle A '\ to bB'A' \ mid bA '\ mid bB' \ mid b}
B→bB′∣b{\ displaystyle B \ to bB '\ b közepe}
B′→vs.VS′B′∣vs.B′∣vs.VS′∣vs.{\ displaystyle B '\ to cC'B' \ mid cB '\ mid cC' \ mid c}
VS→vs.VS′∣vs.{\ displaystyle C \ to cC '\ mid c}
VS′→nál nélNÁL NÉL′VS′∣nál nélVS′∣nál nélNÁL NÉL′∣nál nél{\ displaystyle C '\ to aA'C' \ mid aC '\ mid aA' \ mid a}
Egyéb normális formák
Másodfokú normál forma
A nyelvtan Greibach másodfokú normál alakjában van, ha az összes szabály formájú
NÁL NÉL→nál nélV{\ displaystyle A \ to aV}ahol legfeljebb két változóból áll, tehát ha ezen felül a szabályok megfelelő tagjai legfeljebb 3 hosszúak. A fenti nyelvtan és a nyelvtan:
V{\ displaystyle V}
S→nál nélSS|b{\ displaystyle S \ to aSS | b}a Lukasiewicz nyelv kvadratikus formában van, nyelvtan
S→nál nélSSS|b{\ displaystyle S \ az aSSS-hez | b}nem. Az egymást követő események csoportosításával kvadratikus nyelvtanra alakítható át; itt egy új változót vezetünk be, és a nyelvtan helyébe a következő lép:
T{\ displaystyle T}
S→nál nélST|b,T→SS{\ displaystyle S \ aST-hez | b, \ quad T \ SS-hez}A nyelvtan nem normális Greibach formában, de mint korábban, akkor cserélje ki a vezető változót a szabály , amely ezáltal
T{\ displaystyle T}T→nál nélSSSS∣bS{\ displaystyle T \ to aSSSS \ bs közepe}
S→nál nélST|b,T→nál nélTT∣bS{\ displaystyle S \ aST | b-ig, \ quad T \ aTT \ közepéig bS}.
Kétoldalú normál forma
A nyelvtan kétoldalú normál formában vagy kettős normál Greibach alakban van, ha minden szabálya végződéssel kezdődik és végződik, formailag, ha a szabályok megfelelő tagjai tartózkodnak , hol és hol vannak a nyelvtan terminális és nem terminális ábécéje. A nyelvtan kvadratikus kétoldalú normális formában van, ha a szabályok megfelelő tagjai vannak , tehát ha a szabályok megfelelő tagjai hossza kisebb vagy egyenlő, mint 4. Ezt az konstrukciót Günter Hotz vezette be.
Σ∪ΣV∗Σ{\ displaystyle \ Sigma \ cup \ Sigma V ^ {*} \ Sigma}Σ{\ displaystyle \ Sigma}V{\ displaystyle V}Σ∪Σ(ε∪V∪V2)Σ{\ displaystyle \ Sigma \ cup \ Sigma (\ varepsilon \ cup V \ cup V ^ {2}) \ Sigma}
Egyéb konstrukciók
Egy másik, algebraibb konstrukciót javasolt Daniel J. Rosenkrantz. Alapja egy egyenletrendszer megoldása a részek algebrájában egy szabad monoidon. Ez a módszer közvetlenül másodfokú nyelvtanhoz vezet, ha Chomsky normál formájú nyelvtanból indulunk ki . Más konstrukciókat és általánosításokat különféle szerzők adtak.
Megjegyzések és hivatkozások
-
Hopcroft és Ullman 1979 , p. 95.
-
(in) Sheila A. Greibach , " A New Normal-Form tétel Környezetfüggetlen nyelvtanok mondat szerkezete " , Journal of the ACM , vol. 12, n o 1,1965. január, P. 42–52 ( DOI 10.1145 / 321250.321254 ).
-
(in) Norbert Blum és 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 olvasás ).
-
Ami Chomsky Normál Formájának felépítését illeti, bevezetünk egy új változót, amely axiómává válik, és egyetlen további szabályt , ahol a régi axióma található.S0{\ displaystyle S_ {0}}S0→S{\ displaystyle S_ {0} \ - S}S{\ displaystyle S}
-
Hopcroft, Motwani és Ullman 2007 , p. 268.
-
2008. karton .
-
Günter Hotz, „ A kontextus nélküli nyelvtanok normál alakváltozásai ”, Acta Cybernetica , vol. 4, n o 1,
1978, P. 65-84.
-
(in) Joost Engelfriet , " Egy elemi bizonyítéka kettős Greibach normál forma " , Information Processing Letters , vol. 44, n o 6,
1992, P. 291-293 ( DOI 10.1016 / 0020-0190 (92) 90101-Z ).
-
Daniel J. Rosenkrantz, „ Mátrixegyenletek és normálalak a kontextusmentes nyelvtanokhoz ”, Journal of the ACM , vol. 14, n o 3,
1967. július, P. 501–507.
-
(in) Ryo Yoshinaka , " Egy elemi bizonyítéka általánosítás szabályos dupla Greibach forma " , Information Processing Letters , vol. 109, n o 10,2009, P. 490–492 ( DOI 10.1016 / j.ipl.2009.01.015 ).
Bibliográfia
Kézikönyvek
-
Olivier Carton, Hivatalos nyelvek, kiszámíthatóság és összetettség: matematika vagy informatika alap- és mesterképzés, matematika összesítésének informatikai lehetősége , Párizs, Vuibert,2008, 237 o. ( ISBN 978-2-7117-2077-4 , online olvasás ) - 2.5. Szakasz Normál forma Greibach.
- John E. Hopcroft és Jeffrey D. Ullman , Bevezetés az automata elméletbe, a nyelvek és a számítás , Addison-Wesley,1979
- (en) John E. Hopcroft , Rajeev Motwani és Jeffrey D. Ullman , Bevezetés az automata elméletbe, a nyelvek és a számítás , Addison-Wesley ,2007, 3 e . ( ISBN 978-0-32146225-1 )
-
(en) John E. Hopcroft, Rajeev Motwani és Jeffrey D. Ullman, Bevezetés az automata elméletbe, a nyelvek és a számításokba , Pearson Addison Wesley,2007, 3 e . , xvii + 535 o. ( ISBN 978-0-321-45536-9 és 0-321-45536-3 ) - 277. oldal.
-
(en) Peter Linz, Bevezetés a hivatalos nyelvekbe és automatákba , Jones és Bartlett Learning,2001, 410 p. ( ISBN 978-0-7637-1422-2 és 0763714224 , online olvasás ).
-
de) Katrin Erk és Lutz Priese, Theoretische Informatik: eine umfassende Einführung , Berlin, Springer,2008, 485 p. ( ISBN 978-3-540-76319-2 , OCLC 244015158 ) - 6.8.1 6.3 Chomsky- und Greibach-Normalform p. 121 .
-
(en) Michael A. Harrison, Bevezetés a hivatalos nyelvelméletbe , Olvasás, szentmise. ua, Addison-Wesley,1978, 594 p. ( ISBN 0-201-02955-3 , OCLC 266962302 ) - 4.6. Szakasz: Greibach normál forma, p. 111-120 .
Osztályok
Lásd is
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">