Normální forma Greibacha

V teoretické informatice , a zejména v teorii formálního jazyka , je algebraická gramatika v Greibachově normální formě (v angličtině, Greibachově normální formě nebo GNF ), pokud správní členové jejích pravidel začínají symbolem terminálu , případně následovaným a nebo více proměnné . Varianta umožňuje dalšímu pravidlu vygenerovat prázdné slovo, pokud je součástí jazyka. Tato normální forma je pojmenována po Sheile Greibachové, která ji představila a prokázala svou existenci.

Existují i ​​jiné normální formy gramatiky, jako je Chomského normální forma , nebo gramatiky bez levé rekurze . Normální forma Greibacha je nejkomplikovanější z těchto normálních forem a byla dále vylepšena.

Popis

Algebraická gramatika je v Greibachově normální formě, pokud jsou všechna její pravidla ve tvaru:

NA→naNA1NA2⋯NAne{\ displaystyle A \ až aA_ {1} A_ {2} \ cdots A_ {n}}

nebo

S→ε{\ displaystyle S \ to \ varepsilon}

kde je proměnná , je písmeno a je možná prázdná sekvence proměnných; je axiom a ε je prázdné slovo . NA{\ displaystyle A}na{\ displaystyle a}NA1NA2...NAne{\ displaystyle A_ {1} A_ {2} \ ldots A_ {n}}S{\ displaystyle S}

Gramatika v normální Greibachově podobě je pozoruhodně bez levé rekurze . Hlavní vlastností je, že jakoukoli algebraickou gramatiku lze transformovat do ekvivalentní gramatiky v normální formě Greibacha, teorém založený v roce 1965 Sheilou Greibachovou.

Existuje několik konstrukcí. Pokud neexistuje žádné pravidlo epsilon , je algoritmus jednodušší; v obecném případě dochází k časovým transformacím složitosti a v případě, že gramatika nemá pravidlo jednotky (ve formě proměnné ). S→ε{\ displaystyle S \ to \ varepsilon}Ó(ne4){\ displaystyle O (n ^ {4})}Ó(ne3){\ displaystyle O (n ^ {3})}NA→B{\ displaystyle A \ až B}B{\ displaystyle B}

V normální Greibachově formě derivace generuje v každém kroku derivace písmeno daného jazykového slova: délka derivace se proto rovná délce slova. Normální formu lze použít ekvivalentním způsobem k vytvoření tlačítkového automatu, který přijímá slova jazyka v reálném čase, to znamená čte písmeno vstupního slova v každém kroku výpočtu.

Konstrukce

Konstrukce gramatiky v normální formě Greibacha z algebraické gramatiky dané částí předmětů zpracovaných v mnoha teoretických počítačových učebnicích formálních jazyků, automatů a jejich složitosti. Jedna ze staveb je v několika fázích:

Předběžná fáze: odstranění pravidel epsilon

Můžeme předpokládat, že axiom gramatiky se neobjevuje u pravého člena pravidla.

Pravidlo , kde axiom není, je odstraněno; vezmeme v úvahu každé pravidlo, kde se objeví , a přidáme pro každý výskyt pravidlo do gramatiky, pokud nevytvoříme pravidlo epsilon. Například pokud NA→ε{\ displaystyle A \ to \ varepsilon}NA{\ displaystyle A}B→α{\ displaystyle B \ až \ alfa}NA{\ displaystyle A}α{\ displaystyle \ alpha}α=βNAy{\ displaystyle \ alpha = \ beta A \ gamma}B→βy{\ displaystyle B \ až \ beta \ gama}

B→naNAbNAvs.{\ displaystyle B \ na aAbAc}

přidáme tři pravidla

B→nabNAvs.,B→naNAbvs.,B→nabvs.{\ displaystyle B \ to abAc, B \ to aAbc, B \ to abc}.

Pravidlo, jehož pravý člen obsahuje proměnné, které jsou všechny odvozeny od prázdného slova, se tak může vzdát nových pravidel. ne{\ displaystyle n}2ne{\ displaystyle 2 ^ {n}}

Druhá fáze: odstranění pravidel jednoty

Pravidlo jednotka je pravidlo formy , kde je proměnná. Abychom tento typ pravidla vyloučili, nahradíme takové pravidlo pravidlem NA→B{\ displaystyle A \ až B}B{\ displaystyle B}

NA→α{\ displaystyle A \ až \ alfa}

pro každé pravidlo

B→α{\ displaystyle B \ až \ alfa}

(pokud se nejedná o dříve odstraněné pravidlo jednotky). Tato technika je dokončena v případě cyklů (například existence tří pravidel ) identifikací proměnných cyklu: všechny jsou nahrazeny jednou z nich. NA→B,B→VS,VS→NA{\ displaystyle A \ až B, B \ až C, C \ až A}

Formátování normální

Předpokládáme gramatiku bez pravidel ε a bez pravidel jednotek. Předpokládáme číslované proměnné  ; definujeme posloupnost gramatik, kde je počáteční gramatika, s tou vlastností, že se proměnné neobjeví v čele správných členů pravidla. Předpokládáme, že gramatika je konstruována, a postupujeme ve dvou fázích NA1,NA2,...,NAm{\ displaystyle A_ {1}, A_ {2}, \ tečky, A_ {m}}G0,G1,...,Gne{\ displaystyle G_ {0}, G_ {1}, \ tečky, G_ {n}}G0{\ displaystyle G_ {0}}Gi{\ displaystyle G_ {i}}NA1,...,NAi{\ displaystyle A_ {1}, \ ldots, A_ {i}}Gi-1{\ displaystyle G_ {i-1}}

1. Odstranění levé rekurze proNAi{\ displaystyle A_ {i}}  : odstraníme záhlaví pravidel z  : pravidel NAi{\ displaystyle A_ {i}}NAi{\ displaystyle A_ {i}}

NAi→NAiα1∣...∣NAiαne∣β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}}

kde jsou nezačínají nahrazeny βj{\ displaystyle \ beta _ {j}}NA{\ displaystyle A}

NAi→β1NAi′∣...∣βmNAi′∣β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}} NAi′→α1NAi′∣...∣αneNAi′∣α1∣...∣αne{\ displaystyle A '_ {i} \ rightarrow \ alpha _ {1} A' _ {i} \ mid \ ldots \ mid \ alpha _ {n} A '_ {i} \ mid \ alpha _ {1} \ mid \ ldots \ mid \ alpha _ {n}}

2. Odstranění hlavičkovýchNAi{\ displaystyle A_ {i}}  výskytů: výskyty proměnných, které se objevují nebo se mohou objevit v hlavičce v pravých členech pravidel, jsou nahrazeny sadou pravidel pro tyto proměnné. NAj(1≤j≤i){\ displaystyle A_ {j} (1 \ leq j \ leq i)}

Pokud na konci zůstanou v pravých členech pravidel jiná než v záhlaví koncová písmena, budou nahrazena další proměnnou , jednou pro každé písmeno , s pravidlem . Tna{\ displaystyle T_ {a}}na{\ displaystyle a}Tna→na{\ displaystyle T_ {a} \ to a}

Příklad

Zde je příklad z knihy Oliviera Cartona (píšeme místo ): NA,B,VS{\ displaystyle A, B, C}NA1,NA2,NA3{\ displaystyle A_ {1}, A_ {2}, A_ {3}}

Gramatika G 0  :

NA→NAB∣na{\ displaystyle A \ až AB \ mid a} B→BVS∣b{\ displaystyle B \ až BC \ střední b} VS→VSNA∣vs.{\ displaystyle C \ až CA \ mid c}

Obě pravidla jsou nahrazena NA{\ displaystyle A}

NA→naNA′∣na,NA′→BNA′∣B{\ displaystyle A \ do aA '\ mid a, \ quad A' \ do BA '\ mid B}.

Získáváme:

Gramatika G 1  :

NA→naNA′∣na{\ displaystyle A \ až aA '\ střední a} NA′→BNA′∣B{\ displaystyle A '\ do BA' \ střední B} B→BVS∣b{\ displaystyle B \ až BC \ střední b} VS→VSNA∣vs.{\ displaystyle C \ až CA \ mid c}

Obě pravidla jsou nahrazena B{\ displaystyle B}

B→bB′∣b,B′→VSB′∣VS{\ Displaystyle B \ až bB '\ mid b, \ quad B' \ až CB '\ mid C}a výskyty v horní části B{\ displaystyle B}

jsou nahrazena těmito dvěma pravidly. Získáváme:

Gramatika G 2  :

NA→naNA′∣na{\ displaystyle A \ až aA '\ střední a} NA′→bB′NA′∣bNA′∣bB′∣b{\ displaystyle A '\ to bB'A' \ mid bA '\ mid bB' \ mid b} B→bB′∣b{\ displaystyle B \ až bB '\ střední b} B′→VSB′∣VS{\ displaystyle B '\ do CB' \ střední C} VS→VSNA∣vs.{\ displaystyle C \ až CA \ mid c}

Podobně jsou dvě pravidla nahrazena, v prvním kroku, VS{\ displaystyle C}

VS→vs.VS′∣vs.,VS′→NAVS′∣NA{\ displaystyle C \ to cC '\ mid c, \ quad C' \ to AC '\ mid A},

ale přední proměnná je nahrazena jejími pravidly, stejně jako přední proměnná . Dostaneme gramatiku: NA{\ displaystyle A}VS{\ displaystyle C}

Gramatika G 3

NA→naNA′∣na{\ displaystyle A \ až aA '\ střední a} NA′→bB′NA′∣bNA′∣bB′∣b{\ displaystyle A '\ to bB'A' \ mid bA '\ mid bB' \ mid b} B→bB′∣b{\ displaystyle B \ až bB '\ střední b} B′→vs.VS′B′∣vs.B′∣vs.VS′∣vs.{\ displaystyle B '\ až cC'B' \ střední cB '\ střední cC' \ střední c} VS→vs.VS′∣vs.{\ displaystyle C \ až cC '\ střední c} VS′→naNA′VS′∣naVS′∣naNA′∣na{\ displaystyle C '\ do aA'C' \ střední aC '\ střední aA' \ střední a}

Jiné běžné formy

Kvadratická normální forma

Gramatika je v Greibachově kvadratické normální formě, pokud jsou všechna její pravidla v podobě

NA→naPROTI{\ displaystyle A \ až aV}

kde se skládá z nejvýše dvou proměnných, takže pokud navíc mají správní členové pravidel délku nejvýše 3. Výše ​​uvedená gramatika a gramatika: PROTI{\ displaystyle V}

S→naSS|b{\ Displaystyle S \ ASS | b}

jazyk Lukasiewicz jsou v kvadratické formě, gramatiky

S→naSSS|b{\ displaystyle S \ k aSSS | b}

není. Lze jej transformovat do kvadratické gramatiky seskupením po sobě jdoucích výskytů; zde představíme novou proměnnou a gramatiku nahradíme: T{\ displaystyle T}

S→naST|b,T→SS{\ displaystyle S \ k AST | b, \ quad T \ k SS}

Gramatika již není v normální Greibachově formě, ale stejně jako dříve nahradíme přední proměnnou v pravidle pro , což dává , tedy T{\ displaystyle T}T→naSSSS∣bS{\ displaystyle T \ k aSSSS \ mid bS}

S→naST|b,T→naTT∣bS{\ displaystyle S \ k AST | b, \ quad T \ k aTT \ mid bS}.

Bilaterální normální forma

Gramatika je v normální formě oboustranného nebo normální formě duálního z Greibachové-li spustit všechna její pravidla a konec s koncovou dopisem formálně pokud pravidla členů práv ve kterém a je abeceda terminál a non-terminál gramatiky. Gramatika je v bilaterální kvadratické normální formě, pokud jsou v ní praví členové pravidel , takže pokud jsou navíc praví členové pravidel v délce menší nebo rovné 4. Tuto konstrukci představil Günter Hotz. Σ∪ΣPROTI∗Σ{\ displaystyle \ Sigma \ cup \ Sigma V ^ {*} \ Sigma}Σ{\ displaystyle \ Sigma}PROTI{\ displaystyle V}Σ∪Σ(ε∪PROTI∪PROTI2)Σ{\ displaystyle \ Sigma \ cup \ Sigma (\ varepsilon \ cup V \ cup V ^ {2}) \ Sigma}

Ostatní stavby

Jinou algebraickou konstrukci navrhl Daniel J. Rosenkrantz. Je založen na řešení soustavy rovnic v algebře částí na volném monoidu. Tato metoda vede přímo k kvadratické gramatice, pokud vycházíme z gramatiky v Chomského normální formě . Další konstrukce a zevšeobecnění byly dány různými autory.

Poznámky a odkazy

1. Hopcroft a Ullman 1979 , str.  95.
2. (in) Sheila A. Greibach , „  The New Normal-Form Theorem for Context-Free Grammars Sentence Structure  “ , Journal of ACM , vol.  12, n o  1,Leden 1965, str.  42–52 ( DOI  10.1145 / 321250.321254 ).
3. (in) Norbert Blum a Robert Koch , „  Greibach Normal Form Transformation Revisited  “ , Information & Computation , sv.  150, n o  1, 1999, str.  112–118 ( DOI  10.1006 / inco.1998.2772 , číst online ).
4. Představujeme, co se týče konstrukce Chomského normální formy , novou proměnnou, která se stává axiomem, a jediné další pravidlo , kde je starý axiom.S0{\ displaystyle S_ {0}}S0→S{\ displaystyle S_ {0} \ to S}S{\ displaystyle S}
5. Hopcroft, Motwani a Ullman 2007 , s.  268.
6. Carton 2008 .
7. Günter Hotz, „  Normální tvarové transformace bezkontextových gramatik  “, Acta Cybernetica , roč.  4, n o  1, 1978, str.  65-84.
8. (in) Joost Engelfriet , „  Elementární důkaz dvojí normální formy Greibacha  “ , Information Processing Letters , sv.  44, n O  6, 1992, str.  291–293 ( DOI  10.1016 / 0020-0190 (92) 90101-Z ).
9. Daniel J. Rosenkrantz, „  Maticové rovnice a normální tvary pro bezkontextové gramatiky  “, Journal of ACM , sv.  14, N O  3, července 1967, str.  501–507.
10. (in) Ryo Yoshinaka , „  Elementární důkaz zobecnění pravidelné dvojité Greibachovy formy  “ , Information Processing Letters , sv.  109, n o  10,2009, str.  490–492 ( DOI  10.1016 / j.ipl.2009.01.015 ).

Bibliografie

Manuály

• Olivier Carton, Formální jazyky, vyčíslitelnost a složitost: bakalářský a magisterský titul z matematiky nebo informatiky, výpočetní technika možnost agregace matematiky , Paříž, Vuibert,2008, 237  s. ( ISBN  978-2-7117-2077-4 , číst online ) - Oddíl 2.5 Normální forma Greibach.
• John E. Hopcroft a Jeffrey D. Ullman , Úvod do teorie automatů, jazyky a výpočty , Addison-Wesley,1979
• (en) John E. Hopcroft , Rajeev Motwani a Jeffrey D. Ullman , Úvod do teorie automatů, jazyků a výpočtů , Addison-Wesley ,2007, 3 e  ed. ( ISBN  978-0-32146225-1 )
• (en) John E. Hopcroft, Rajeev Motwani a Jeffrey D. Ullman, Úvod do teorie automatů, jazyků a výpočtů , Pearson Addison Wesley,2007, 3 e  ed. , xvii + 535  str. ( ISBN  978-0-321-45536-9 a 0-321-45536-3 ) - strana 277.
• (en) Peter Linz, Úvod do formálních jazyků a automatů , Jones & Bartlett Learning,2001, 410  str. ( ISBN  978-0-7637-1422-2 a 0763714224 , číst online ).
• (de) Katrin Erk a Lutz Priese, Theoretische Informatik: eine umfassende Einführung , Berlin, Springer,2008, 485  s. ( ISBN  978-3-540-76319-2 , OCLC  244015158 ) - 6.8.1 6.3 Chomsky- und Greibach-Normalform str.  121 .
• (en) Michael A. Harrison, Úvod do teorie formálního jazyka , čtení, mše sv. ua, Addison-Wesley,1978, 594  s. ( ISBN  0-201-02955-3 , OCLC  266962302 ) - Oddíl 4.6 Greibachova normální forma, s.  111-120 .

Třídy

• Arthur Milchior, "  Normální forma Greibacha  " , Kurzy psaní ENS (Olivier Carton) ,19. prosince 2008.
• Jacques Désarménien, „  Kapitola 4.4 Normální forma Greibacha  “ , Cours automatizuje , Université Paris-Est Marne-la-Vallée .
• Sandrine Julia, „  Course 7 - Grammaires out of context (pokračování)  “ , Automates & Langages , University of Nice - Sophia Antipolis .

Podívejte se také

• Backus-Naurova forma
• Chomsky normální forma
• Normální forma Kuroda  (en)

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">