Poznámky k cvičeniu č. 3
Peter Kostolányi
9. októbra 2014
Formálna definícia pojmu odvodenia
Odvodenie v bezkontextovej gramatike je pomerne intuitívny pojem, ktorého poriadnej definícii
sa v literatúre nevenuje príliš veľká pozornosť. Zvyčajne sa narába iba s neformálnou predstavou
o „odvodení σ ⇒ w1 ⇒ . . . ⇒ wn “ , pričom sa toleruje, že takýto zápis v skutočnosti nereprezentuje žiaden matematický objekt. V niektorých zdrojoch možno nájsť pokus o zmiernenie tejto
nepresnosti podaním formálnej definície pojmu odvodenia, ktorá má zápisom ako ten vyššie priradiť určitý význam. Tieto definície sú však často chybné a nesúhlasia napríklad s teóriou okolo
stromov odvodenia, kde je čitateľ znova prenechaný napospas intuícii.
Hovoriť o „odvodení σ ⇒ w1 ⇒ . . . ⇒ wn “ je účelné z hľadiska prehľadnosti a intuitívnosti
zápisu a budeme tak robiť aj my. Na správne pochopenie konceptu stromov odvodenia je však
nutné mať adekvátnu predstavu o tom, čo sa takýmto zápisom v skutočnosti myslí. Inými slovami,
je nutná formálna definícia pojmu odvodenia, ktorá bude „v pozadí“ za každým zápisom typu
σ ⇒ w1 ⇒ . . . ⇒ wn a ktorá zároveň bude v súlade s neskoršie zavedenými pojmami.
Začnime najprv s nepresnou definíciou Seymoura Ginsburga.1 Ten definuje odvodenie ako
postupnosť slov w0 , w1 , . . . , wn takých, že platí w0 ⇒ w1 ⇒ . . . ⇒ wn . Uvažujme ale napríklad
odvodenie vetnej formy ααα v bezkontextovej gramatike (N, T, P, σ) s N = {σ, α}, T = {a} a
P = {σ → αα, α → αα | a}. Podľa Ginsburgovej definície zjavne existuje jediné takéto odvodenie
σ ⇒ αα ⇒ ααα,
čo zodpovedá postupnosti slov σ, αα, ααα. Zaveďme však teraz do obvyklého zápisu odvodení nový
prvok: v každej vetnej forme podčiarknime ten výskyt neterminálu, ktorý sa v nasledujúcom kroku
odvodenia prepíše. Ľahko vidieť, že takýmto spôsobom vieme pre slovo ααα nájsť dve odvodenia,
ktoré intuitívne nie sú ekvivalentné:
σ ⇒ αα ⇒ ααα,
σ ⇒ αα ⇒ ααα.
Tieto dve odvodenia nie sú ekvivalentné nielen intuitívne, ale ani podľa neskoršej Ginsburgovej
definície stromu odvodenia. Z toho vyplýva, že definícia odvodenia ako postupnosti slov v relácii
kroku odvodenia nie je postačujúca.
Poznámka 1. Problém s odvodením vetnej formy ααα v gramatike G by nevyriešila ani definícia odvodenia ako striedavej postupnosti slov a prepisovacích pravidiel. Tá je totiž pri obidvoch
neekvivalentných odvodeniach rovnaká.
Vhodnou nápravou Ginsburgovej definície sa javí byť práve zahrnutie „podčiarknutých neterminálov“ použitých vyššie. Zo zápisu uαv ⇒ uxv je totiž zrejmý výskyt prepisovaného neterminálu
a aj použité prepisovacie pravidlo je ním určené jednoznačne (prečo?).
Definícia 1. Nech G = (N, T, P, σ) je bezkontextová gramatika. Nech N = {α | α ∈ N } je
abeceda „podčiarknutých neterminálov“ , o ktorej predpokladáme, že je disjunktná s N . Nech
h : (N ∪ N ∪ T )∗ → (N ∪ T )∗ , definovaný ako h(α) = α a h(α) = α pre α ∈ N a ako h(c) = c pre
c ∈ T , je „homomorfizmus vymazávajúci podčiarknutia“ . Odvodenie v gramatike G je postupnosť
slov w0 , w1 , . . . , wn taká, že:
∗
∗
(i) Pre i = 0, . . . , n − 1, wi = ui αi vi , kde ui , vi ∈ (N ∪ T ) a αi ∈ N ; wn ∈ (N ∪ T ) .
∗
(ii) Pre i = 0, . . . , n − 1, h(wi+1 ) = ui xi vi pre nejaké xi ∈ (N ∪ T ) také, že αi → xi ∈ P .
Odvodenie slova w v gramatike G je odvodenie w0 , w1 , . . . , wn také, že w0 = σ a wn = w.
1 Ginsburg,
S.: The Mathematical Theory of Context Free Languages. McGraw-Hill, 1966.
1
Stromy odvodenia, jednoznačnosť a viacznačnosť
Nie je však pravdou, že všetky formálne rôzne odvodenia sú aj intuitívne neekvivalentné. Uvažujme
napríklad gramatiku G z predchádzajúceho oddielu. Slovo aa sa v nej dá odvodiť dvoma spôsobmi:
σ ⇒ αα ⇒ aα ⇒ aa,
σ ⇒ αα ⇒ αa ⇒ aa.
Tieto odvodenia sa líšia iba poradím prepísania jednotlivých výskytov neterminálu α, pričom
„štruktúra“ odvodenia je v oboch prípadoch rovnaká. Podobná situácia nastane vždy, keď sa
v odvodení vyskytne vetná forma s viac ako jedným neskôr prepísaným neterminálom – poradie
ich prepisovania možno zvoliť ľubovoľne, čo znamená viacero formálne rôznych odvodení.
Aj z tohto dôvodu je často namieste považovať odvodenia s rovnakou „štruktúrou“ , líšiace sa iba
poradím prepisovania neterminálov, za ekvivalentné. Formalizáciou takejto intuitívnej štruktúry je
strom odvodenia, čo je stromová štruktúra jedinečná pre každé odvodenie.2 Stromu odvodenia môže
naopak zodpovedať aj viacero odvodení, ktoré sa však líšia iba poradím prepisovania neterminálov
a považujú sa za „ekvivalentné“ .
Prv než uvedieme jeho formálnu definíciu, ilustrujeme pojem stromu odvodenia na príklade.
Príklad 1. Uvažujme gramatiku G = (N, T, P, σ) s N = {σ}, T = {a, b} a P = {σ → σσ | a | b | ε}
a odvodenia
σ ⇒ σσ ⇒ σσσ ⇒ aσσ ⇒ abσ ⇒ aba
σ ⇒ σσ ⇒ σσσ ⇒ σσσσ ⇒ aσσσ ⇒ aσσ ⇒ abσ ⇒ aba.
Zodpovedajúce stromy odvodenia sú na obrázku 1.
σ
σ
σ
σ
σ
σ
a
b
σ
a
σ
σ
σ
σ
σ
a
ε
b
a
(b) Strom druhého odvodenia.
(a) Strom prvého odvodenia.
Obr. 1: Stromy odvodení v gramatike G.
Stromy odvodenia zodpovedajúce daným dvom odvodeniam slova aba sú rôzne, čo znamená,
že tieto dve odvodenia nepovažujeme za „ekvivalentné“ . Naopak, napríklad odvodenie
σ ⇒ σσ ⇒ σa ⇒ σσa ⇒ σba ⇒ aba
má rovnaký strom odvodenia ako prvé odvodenie. Tieto dve odvodenia teda možno považovať za
v určitom zmysle ekvivalentné.
Formálna definícia stromu odvodenia zvyčajne pozostáva z dvoch častí. V prvej sa definujú
všetky korektné stromy odvodení v danej gramatike. V druhej časti sa potom definuje, kedy strom
odvodenia zodpovedá nejakému odvodeniu. V nasledujúcom pod stromom rozumieme zakorenený
strom s ohodnotenými uzlami a s pevným usporiadaním potomkov.
Definícia 2. Nech G = (N, T, P, σ) je bezkontextová gramatika. Strom odvodenia v gramatike G
je strom, pre ktorý sú splnené nasledujúce podmienky:
(i) Každý vnútorný uzol je ohodnotený nejakým neterminálom ξ ∈ N .
2 Pre
Ginsburgovu menej presnú definíciu odvodenia táto vlastnosť (nechtiac) neplatí.
2
(ii) Každý list je ohodnotený buď nejakým symbolom d ∈ N ∪ T , alebo prázdnym slovom ε.
Listy ohodnotené prázdnym slovom nemajú súrodencov.
(iii) Ak má uzol ohodnotený neterminálom ξ ∈ N synov ohodnotených d1 , . . . , dn ∈ N ∪ T ∪ {ε}
(v tomto poradí), tak pravidlo ξ → d1 . . . dn ∈ P .
Zreťazenie ohodnotení všetkých listov (v poradí zľava doprava) určuje vetnú formu vygenerovanú daným odvodením z neterminálu, ktorým je ohodnotený koreň.
Definícia 3. Nech G = (N, T, P, σ) je bezkontextová gramatika a ξ ⇒n w je odvodenie v G,3
∗
kde n ∈ N, ξ ∈ N a w ∈ (N ∪ T ) . Strom odvodenia ξ ⇒n w je strom odvodenia v gramatike
G so zreťazením ohodnotení listov (v poradí zľava doprava) rovným w, definovaný induktívne
vzhľadom na n:
1. Pre n = 0 je w = ξ a strom odvodenia ξ ⇒0 ξ je strom pozostávajúci z jedného uzla
ohodnoteného ξ.
2. Strom odvodenia ξ ⇒n uαv ⇒ uxv = w vznikne zo stromu odvodenia ξ ⇒n uαv pridaním
synov jeho (|u| + 1)-ému listu tak, aby zreťazenie ich ohodnotení bolo x.
Poznámka 2. Uvedená definícia nie je úplne poriadna, čo nie je iba záležitosťou používania prirodzeného jazyka namiesto formalizmov, ale aj skutočnosti, že jej implicitnou súčasťou je nedokázané
tvrdenie: „každý strom zostrojený podľa uvedenej induktívnej definície je strom odvodenia a zreťazenie ohodnotení jeho listov (v poradí zľava doprava) je rovné výslednej vetnej forme daného
odvodenia.“ Formálny dôkaz tohto tvrdenia, bez ktorého by definícia 3 nedávala zmysel, prenechávame čitateľovi.
Je ľahké dokázať, že ľubovoľný podstrom stromu odvodenia, okrem samotných listov ohodnotených terminálom alebo prázdnym slovom, je sám tiež stromom odvodenia.
Ľavé krajné odvodenie je také odvodenie w0 , w1 , . . . , wn (v zmysle definície 1), kde je vo všetkých vetných formách w0 , . . . , wn−1 podčiarknutý prvý výskyt neterminálu (zľava) a pravé krajné
odvodenie je také odvodenie, kde sú podčiarknuté posledné výskyty neterminálov. Inými slovami,
v ľavom krajnom odvodení sa v každom kroku odvodenia prepisuje prvý neterminál zľava a v pravom krajnom odvodení sa v každom kroku prepisuje prvý neterminál sprava. Krok ľavého krajného
odvodenia sa niekedy zvykne označovať symbolom ⇒lm a krok pravého krajného odvodenia symbolom ⇒rm .
Ľahko vidieť, že existuje vzájomne jednoznačná korešpondencia medzi stromami odvodenia
a ľavými (resp. pravými) krajnými odvodeniami.
Definícia 4. Nech G = (N, T, P, σ) je bezkontextová gramatika. Gramatika G sa nazýva jednoznačná, ak pre každé slovo w ∈ L(G) existuje práve jedno ľavé krajné odvodenie v gramatike G.
Gramatika, ktorá nie je jednoznačná, sa nazýva viacznačná.
Definícia 5. Nech L ∈ LCF je bezkontextový jazyk. Jazyk L sa nazýva jednoznačný, ak existuje
jednoznačná bezkontextová gramatika G taká, že L(G) = L. Jazyk, ktorý nie je jednoznačný, sa
nazýva vnútorne viacznačný.
Čitateľ si už istotne uvedomil, že jednoznačnosť gramatiky je ekvivalentná s podmienkou existencie práve jedného pravého krajného odvodenia, čo je ďalej ekvivalentné tomu, že pre každé slovo
w ∈ L(G) existuje práve jeden strom jeho odvodenia.
Normálne tvary bezkontextových gramatík
Veta o normálnom tvare bezkontextových gramatík je ľubovoľné tvrdenie, ktoré hovorí, že pre
ľubovoľnú bezkontextovú gramatiku G existuje ekvivalentná gramatika G0 spĺňajúca nejakú netriviálnu podmienku. Inými slovami, definíciu bezkontextovej gramatiky možno zúžiť tak, že sila
modelu ostane nezmenená.4
3 Treba
mať na pamäti, že pod nepresným zápisom ξ ⇒n w chápeme odvodenie v zmysle definície 1.
tvrdenia možno samozrejme študovať aj pre iné objekty, ako sú bezkontextové gramatiky. Jedinou
podmienkou je, aby na danej triede objektov bola netriviálnym spôsobom definovaná ekvivalencia (ktorú v prípade
bezkontextových gramatík možno definovať ako G ∼ G0 ⇐⇒ L(G) = L(G0 )).
4 Podobné
3
Význam takýchto tvrdení spočíva predovšetkým v dvoch rozdielnych druhoch aplikácií:
• Normálne tvary často uľahčujú dôkazy tvrdení o bezkontextových jazykoch. Namiesto všeobecných bezkontextových gramatík totiž stačí uvažovať iba gramatiky v normálnom tvare,
čo môže podstatne zjednodušiť argumentáciu. V takomto prípade je dôležitá iba skutočnosť,
že ekvivalentná gramatika v normálnom tvare existuje; algoritmus na prevod do normálneho
tvaru je tu druhotný.
• Viaceré v praxi užitočné algoritmy pracujúce s bezkontextovými gramatikami5 predpokladajú ako svoj vstup gramatiku v nejakom normálnom tvare. Pri implementácii takýchto
algoritmov sa preto často zíde aj procedúra na prevod do zodpovedajúceho normálneho
tvaru.
V nasledujúcom sa zameriame výlučne na praktickú stránku prevodu gramatík do jednotlivých normálnych tvarov. Formálne matematické zápisy týchto konštrukcií a dôkazy ich správnosti
boli prebraté na prednáške. Čitateľ by sa mal uistiť, že je schopný nasledujúce postupy náležite
sformalizovať.
Redukovaný normálny tvar
Bezkontextová gramatika je v redukovanom normálnom tvare, ak neobsahuje žiadne pravidlo typu
ξ → ξ, každý jej neterminál ξ je dosiahnuteľný (teda existuje vetná forma obsahujúca ξ, ktorá je
odvoditeľná z počiatočného neterminálu) a z každého jej neterminálu možno odvodiť aspoň jedno
terminálne slovo.
Definícia 6. Nech G = (N, T, P, σ) je bezkontextová gramatika. Gramatika G je v redukovanom
normálnom tvare, ak sú splnené nasledujúce tri podmienky:
(i) Množina pravidiel P neobsahuje pre žiadne ξ ∈ N pravidlo ξ → ξ.
∗
(ii) Pre každé ξ ∈ N existujú slová u, v ∈ (N ∪ T ) také, že σ ⇒∗ uξv.
(iii) Pre každé ξ ∈ N existuje terminálne slovo w ∈ T ∗ také, že ξ ⇒∗ w.
Pomenovanie normálny tvar je odôvodnené vďaka nasledujúcej vete, ktorá bola dokázaná na
prednáške.
Veta 1. Nech G je bezkontextová gramatika taká, že L(G) 6= ∅. Potom existuje bezkontextová
gramatika G0 v redukovanom normálnom tvare taká, že L(G0 ) = L(G).
Poznámka 3. Predpoklad L(G) 6= ∅ je v predchádzajúcej vete naozaj nutný. Každá bezkontextová
gramatika totiž musí mať definovaný počiatočný neterminál σ. Ak je navyše gramatika G v redukovanom normálnom tvare, musí podľa podmienky (iii) definície 6 existovať terminálne slovo w
také, že σ ⇒∗ w. Toto slovo ale nutne patrí do jazyka L(G).
Uveďme teraz algoritmus prevodu bezkontextovej gramatiky do redukovaného normálneho
tvaru, ktorého korektnosť vyplýva z dôkazu vety 1. Vstupom pre nasledujúci algoritmus je bezkontextová gramatika G = (N, T, P, σ).
1. Zostroj množinu S = {ξ ∈ N | ∃w ∈ T ∗ : ξ ⇒∗G w} „terminujúcich“ neterminálov v gramatike G:
1.1 Nech S0 = {ξ ∈ N | ∃u ∈ T ∗ : ξ → u ∈ P } je množina neterminálov „terminujúcich“
na jeden krok.
1.2 Iteruj Si = Si−1 ∪ {ξ ∈ N | ∃u ∈ (T ∪ Si−1 )∗ : ξ → u ∈ P } pre i = 1, 2, . . ., až kým pre
nejaké k nenastane Sk = Sk−1 .
1.3 S = Sk .
5 Príkladom
môžu byť algoritmy, ktoré pre slovo x a gramatiku G rozhodujú, či x ∈ L(G).
4
2. Odstráň z gramatiky G všetky neterminály z N − S a všetky pravidlá, v ktorých sa takéto
neterminály vyskytujú. Formálne, N1 := S a P1 := {ξ → x ∈ P | ξ ∈ S ∧ x ∈ (S ∪ T )∗ }.
Ak S neobsahuje počiatočný neterminál σ, skonči (G generuje prázdny jazyk). V opačnom
prípade definuj G1 = (N1 , T, P1 , σ) a pokračuj bodom 3.
∗
3. Zostroj množinu H = {ξ ∈ N1 | ∃u, v ∈ (N1 ∪ T ) : σ ⇒∗G1 uξv} dosiahnuteľných neterminálov v gramatike G1 :
3.1 Nech H0 = {σ}.
∗
3.2 Iteruj Hi = Hi−1 ∪ {ξ ∈ N | ∃η ∈ Hi−1 ∃u, v ∈ (N1 ∪ T ) : η → uξv ∈ P1 } pre
i = 1, 2, . . ., až kým pre nejaké k nenastane Hk = Hk−1 .
3.3 H = Hk .
4. Odstráň z gramatiky G1 všetky neterminály z N1 − H a všetky pravidlá, v ktorých sa takéto
neterminály vyskytujú. Formálne, N2 := H a P2 := {ξ → x ∈ P1 | ξ ∈ H}. Ak H = ∅, skonči
(G generuje prázdny jazyk). V opačnom prípade definuj G2 = (N2 , T, P2 , σ) a pokračuj
bodom 5.
5. Odstráň z gramatiky G2 všetky pravidlá ξ → ξ ∈ P2 , ξ ∈ N2 . Formálne, definuj N 0 = N2 a
P 0 = P2 − {ξ → ξ | ξ ∈ N2 }. Vráť ako výstup gramatiku G0 = (N 0 , T, P 0 , σ).
Poznámka 4. Uvedený algoritmus sa na každom vstupe zastaví, čo vyplýva zo skutočnosti, že v krokoch 1.2 a 3.2 sa do množín Si resp. Hi v každej iterácii (okrem poslednej) pridá oproti množinám
Si−1 resp. Hi−1 aspoň jeden neterminál a celkový počet neterminálov je konečný. Skutočnosť, že
množiny Sk resp. Hk sú skutočne hľadané množiny „terminujúcich“ resp. dosiahnuteľných neterminálov, bola dokázaná na prednáške. Dôležité tu ale je, že Sk resp. Hk sú najmenšie nadmnožiny
S0 resp. H0 , ktoré sú iterovaným predpisom nezmenené.
Podobné iteratívne konštrukcie sú v informatike pomerne časté, ale ich analýza nemusí byť
takto jednoduchá. Spoločným znakom je iterácia predpisu xi = F (xi−1 ) na prvkoch z nejakej usporiadanej množiny spĺňajúcej určité podmienky,6 monotónnosť iterovaného zobrazenia F vzhľadom
na dané usporiadanie a podmienka, aby hľadaný výsledok x bol najmenším pevným bodom zobrazenia F nad x0 , t.j. aby platilo F (x) = x a aby x bol najmenší takýto prvok, pre ktorý x0 x.
Existencia pevných bodov a konvergencia iteratívneho postupu potom vyplýva z tzv. viet o pevných bodoch, z ktorých v tomto kontexte možno spomenúť predovšetkým Tarského vetu o pevnom
bode 7 a Kleeneho vetu o pevnom bode.8
Úloha 1. Nech G = (N, T, P, σ) je bezkontextová gramatika s N = {σ, α, β, γ}, T = {a, b} a
P = {σ → aαβ | ββ | α
α → αbα | aa
β → bβγ | ββ
γ → aγ | σ | ε}.
Preveďte gramatiku G do redukovaného normálneho tvaru.
Riešenie. Zostrojíme najprv množinu „terminujúcich“ neterminálov S:
1. S0 = {α, γ},
2. S1 = S0 ∪ {σ, α, γ} = {σ, α, γ},
3. S2 = S1 ∪ {σ, α, γ} = {σ, α, γ} = S1 .
6 Väčšinou
sa požaduje, aby išlo o tzv. úplný zväz alebo úplné čiastočné usporiadanie (CPO).
7 http://en.wikipedia.org/wiki/Knaster-Tarski_theorem
8 http://en.wikipedia.org/wiki/Kleene_fixed-point_theorem
5
Máme teda S = S2 = {σ, α, γ}. Po odstránení „neterminujúcich“ neterminálov tak dostávame
gramatiku G1 = (N1 , T, P1 , σ) s N1 = {σ, α, γ} a P1 = {σ → α, α → αbα | aa, γ → aγ | σ | ε}.
Zostrojme teraz množinu dosiahnuteľných neterminálov v gramatike G1 :
1. H0 = {σ},
2. H1 = H0 ∪ {α} = {σ, α},
3. H2 = H1 ∪ {α} = {σ, α} = H1 .
Dostávame teda H = H2 = {σ, α}. Keďže sa vo vstupnej gramatike nevyskytujú žiadne pravidlá
typu ξ → ξ, výslednú gramatiku v normálnom tvare dostaneme už po odstránení nedosiahnuteľných neterminálov: G0 = (N 0 , T, P 0 , σ), kde N 0 = {σ, α} a P 0 = {σ → α, α → αbα | aa}.
Poznámka 5. Poradie odstraňovania „neterminujúcich“ a nedosiahnuteľných neterminálov vo všeobecnosti nemožno v algoritme prevodu do normálneho tvaru vymeniť. Uvažujme napríklad gramatiku G = (N, T, P, σ) s N = {σ, α}, T = {a} a P = {σ → σα, α → a}. Ľahko možno vidieť, že
L(G) = ∅, a teda horeuvedený algoritmus skončí bez toho, aby vrátil gramatiku G0 . Skúsme teraz
aplikovať opačný postup a uvažujme najprv dosiahnuteľnosť neterminálov. Dostávame H0 = {σ}
a H1 = {σ, α} = H2 = H. Všetky neterminály sú teda dosiahnuteľné. Zamerajme sa teraz na
„terminujúce“ neterminály. Dostávame S0 = {α} = S1 = S. Vo výsledku teda máme N 0 = {α}, čo
je rôzne od prázdnej množiny, a teda nesprávne.9 Po odstránení „neterminujúcich“ neterminálov
sa totiž môžu niektoré pôvodne dosiahnuteľné neterminály stať nedosiahnuteľnými.
Odstraňovanie pravidiel typu ξ → ξ naopak možno robiť aj na začiatku alebo uprostred celého
postupu.
Cvičenie 1. Niektoré zápisy sa zvyknú používať iba kvôli prehľadnosti. Zistite, či v horeuvedenom
algoritme možno v kroku 1.2 iterovať iba Si = {ξ ∈ N | ∃u ∈ (T ∪ Si−1 )∗ : ξ → u ∈ P }. Možno
∗
v kroku 3.2 iterovať iba Hi = {ξ ∈ N | ∃η ∈ Hi−1 ∃u, v ∈ (N1 ∪ T ) : η → uξv ∈ P1 }?
„Bezepsilonový“ normálny tvar
Bezkontextová gramatika je v „bezepsilonovom“ normálnom tvare, ak neobsahujúce vymazávajúce
pravidlá typu ξ → ε. V tomto prípade je pomenovanie „normálny tvar“ mierne zavádzajúce: gramatika bez takýchto pravidiel nikdy nemôže vygenerovať prázdne slovo ε, a teda nie každá bezkontextová gramatika sa dá do „bezepsilonového“ tvaru previesť. Ako však bolo dokázané na prednáške,
ku každej bezkontextovej gramatike G existuje bezkontextová gramatika G0 v „bezepsilonovom“
normálnom tvare, ktorá je s gramatikou G ekvivalentná „až na ε“ , t.j. platí L(G0 ) = L(G) − {ε}.
Definícia 7. Nech G = (N, T, P, σ) je bezkontextová gramatika. Hovoríme, že gramatika G je
+
v „bezepsilonovom“ normálnom tvare, ak P ⊆ N × (N ∪ T )
Veta 2. Nech G = (N, T, P, σ) je bezkontextová gramatika. Potom existuje bezkontextová gramatika G0 = (N 0 , T 0 , P 0 , σ 0 ) v „bezepsilonovom“ normálnom tvare taká, že L(G0 ) = L(G) − {ε}.
Správnosť nasledujúceho algoritmu na prevod gramatiky do „bezepsilonového“ normálneho
tvaru bola dokázaná na prednáške. Vstupom je bezkontextová gramatika G = (N, T, P, σ).
1. Zostroj množinu E = {ξ ∈ N | ξ ⇒∗ ε} vymazávajúcich neterminálov v gramatike G:
1.1 Nech E0 = {ξ ∈ N | ξ → ε ∈ P } je množina neterminálov vymazávajúcich na jeden
krok.
∗
1.2 Iteruj Ei = Ei−1 ∪ {ξ ∈ N | ∃u ∈ Ei−1
: ξ → u ∈ P } pre i = 1, 2, . . ., až kým pre nejaké
k nenastane Ek = Ek−1 .
1.3 E = Ek .
9 Čitateľ
by určite ľahko prišiel aj s kontrapríkladom, kde výsledná množina neterminálov obsahuje počiatočný
neterminál σ a kde teda nie je možné chybný výsledok žiadnym triviálnym spôsobom rozoznať.
6
+
2. Pre každé pôvodné prepisovacie pravidlo ξ → u ∈ P také, že ξ ∈ N a u ∈ (N ∪ T ) , pridaj do
∗
množiny prepisovacích pravidiel všetky pravidlá ξ → v0 v1 . . . vj , j ∈ N, v0 , . . . , vj ∈ (N ∪ T ) ,
také, že pre nejaké α1 , . . . , αj ∈ E platí u = v0 α1 v1 α2 . . . vj−1 αj vj .
3. Odober z množiny prepisovacích pravidiel všetky pravidlá ξ → ε, kde ξ ∈ N . Vráť výslednú
gramatiku G0 = (N 0 , T 0 , P 0 , σ 0 ) ako výstup.
V bode 2 by samozrejme bolo možné pridávať iba také pravidlá ξ → v0 v1 . . . vj , pre ktoré
v0 v1 . . . vj 6= ε. V opačnom prípade sa totiž pravidlo hneď v nasledujúcom kroku z gramatiky
odstráni.
Úloha 2. Nech G = (N, T, P, σ) je bezkontextová gramatika s N = {σ, α, β, γ}, T = {a, b} a
P = {σ → aσ | bα | bb
α → β | aa
β → bββ | ε
γ → αα | aγ | a}.
Preveďte gramatiku G do „bezepsilonového“ normálneho tvaru.
Riešenie. Zostrojíme najprv množinu vymazávajúcich neterminálov E:
1. E0 = {β},
2. E1 = E0 ∪ {α, β} = {α, β},
3. E2 = E1 ∪ {α, β, γ} = {α, β, γ},
4. E3 = E2 ∪ {α, β, γ} = {α, β, γ} = E2 .
Po úprave prepisovacích pravidiel potom dostávame gramatiku G0 = (N, T, P 0 , σ) s
P 0 = {σ → aσ | bα | b | bb
α → β | aa
β → bββ | bβ | b
γ → αα | α | aγ | a}.
Konštrukcia je hotová.
Poznámka 6. Už sme spomenuli, že „bezepsilonový“ normálny tvar nie je normálnym tvarom
v pravom slova zmysle: „bezepsilonové“ gramatiky totiž nedokážu vygenerovať prázdne slovo
a veta o normálnom tvare tak zaručuje iba ekvivalenciu „až na ε“ . Tento drobný problém sa
často zvykne riešiť alternatívnou definíciou „bezepsilonového“ normálneho tvaru, v ktorom sa
toleruje prepisovacie pravidlo σ → ε v prípade, že sa počiatočný neterminál σ nevyskytuje na pravej strane žiadneho pravidla. Inými slovami, množina prepisovacích pravidiel P musí byť v tvare
+
P ⊆ {σ → ε} ∪ N × ((N − {σ}) ∪ T ) . Na prevod do tejto varianty „bezepsilonového“ normálneho
tvaru stačí použiť horeuvedený algoritmus, pridať nový počiatočný neterminál σ 0 , pravidlo σ 0 → σ
a ak σ ∈ E, tak aj pravidlo σ 0 → ε.
Chomského normálny tvar
Chomského normálny tvar zaručuje, že strom odvodenia bezkontextovej gramatiky je (až na listy
ohodnotené terminálnym symbolom alebo prázdnym slovom, ktoré nemajú súrodencov) binárny.
Definícia 8. Nech G = (N, T, P, σ) je bezkontextová gramatika. Gramatika G je v Chomského
normálnom tvare, ak P ⊆ N × (N 2 ∪ T ∪ {ε}).
7
Veta 3. Nech G je bezkontextová gramatika. Potom existuje bezkontextová gramatika G0 v Chomského normálnom tvare taká, že L(G0 ) = L(G).
Dôkaz tejto vety sa preberal na prednáške a tu preto iba uvedieme algoritmus na prevod
gramatiky do Chomského normálneho tvaru. Jeho vstupom je gramatika G = (N, T, P, σ).
1. Pre každý terminál c ∈ T zaveď nový10 neterminál ξc a pravidlo ξc → c.
∗
∗
2. Nech h : (N ∪ T ) → (N ∪ {ξc | c ∈ T }) je homomorfizmus taký, že pre všetky c ∈ T je
h(c) = ξc a pre všetky ξ ∈ N je h(ξ) = ξ. Zmeň všetky pravidlá α → x pôvodnej gramatiky
na α → h(x). Nech G1 = (N1 , T, P1 , σ) je výsledná gramatika.
3. Zaveď nový neterminál ξε a pravidlo ξε → ε. Zmeň všetky pravidlá α → β ∈ P1 , α, β ∈ N1 ,
na α → βξε . Nech G2 = (N2 , T, P2 , σ) je výsledná gramatika.
4. Pre každé pravidlo π : α → β1 β2 . . . βk ∈ P2 , k > 2, β1 , . . . , βk ∈ N2 :
4.1 Zaveď nové neterminály ψπ,1 , . . . , ψπ,k−2 .
4.2 Odober pravidlo α → β1 β2 . . . βk .
4.3 Pridaj pravidlá α → β1 ψπ,1 , ψπ,1 → β2 ψπ,2 , . . . , ψπ,k−2 → βk−1 βk−2 .
Nech G0 = (N 0 , T, P 0 , σ) je výsledná gramatika. Vráť gramatiku G0 ako výstup.
Poznámka 7. Uvedený algoritmus nie je optimálny: napríklad všetky pravidlá α → c, c ∈ T ,
pôvodnej gramatiky (ktoré Chomského normálny tvar neporušujú) sa nahradia trojicou pravidiel
α → ξc ξε , ξc → c a ξε → ε. Poznamenajme však, že toto neplatí pre pravidlá α → ε pôvodnej
gramatiky, ktoré sú vo výsledku nezmenené.
Úloha 3. Nech G = (N, T, P, σ) je bezkontextová gramatika s N = {σ, α, β}, T = {a, b} a
P = {σ → aαbβ | ββ | α
α → αbα | aa
β → bββ | ε}.
Preveďte gramatiku G do Chomského normálneho tvaru.
Riešenie. Pre všetky c ∈ T zaveďme nový neterminál ξc a pravidlo ξc → c a aplikujme príslušnú
transformáciu pravidiel, ktorých množina sa po transformácii zmení na
P1 = {σ → ξa αξb β | ββ | α
α → αξb α | ξa ξa
β → ξb ββ | ε
ξa → a
ξb → b}.
Zaveďme ďalej nový neterminál ξε a pravidlo ξε → ε a vykonajme príslušnú transformáciu pravidiel, čím sa ich množina zmení na
P2 = {σ → ξa αξb β | ββ | αξε
α → αξb α | ξa ξa
β → ξb ββ | ε
ξa → a
ξb → b
ξε → ε}.
10 To
znamená predpoklad, že práve zavedený neterminál nepatrí do N ani do T .
8
„Rozbime“ ešte príliš dlhé pravé strany pravidiel pomocou nových neterminálov. Za týmto účelom
zaveďme označenia pravidiel
π1 : σ → ξa αξb β,
π2 : α → αξb α,
π3 : β → ξb ββ.
Po transformácii z bodu 4 horeuvedeného algoritmu potom dostávame bezkontextovú gramatiku
G0 = (N 0 , T, P 0 , σ) s N 0 = {σ, α, β, ξa , ξb , ξε , ψπ1 ,1 , ψπ1 ,2 , ψπ2 ,1 , ψπ3 ,1 } a
P 0 = {σ → ξa ψπ1 ,1 | ββ | αξε
α → αψπ2 ,1 | ξa ξa
β → ξb ψπ3 ,1 | ε
ψπ1 ,1 → αψπ1 ,2
ψπ1 ,2 → ξb β
ψπ2 ,1 → ξb α
ψπ3 ,1 → ββ
ξa → a
ξb → b
ξε → ε}.
Konštrukcia je týmto dokončená.
9
Download

Poznámky k cvičeniu č. 3