IB102 úkol 10, příklad 1 Odevzdání: 3. 12. 2018
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
1. [2 body] Uvažte následující gramatiku G:
G = ({A, B, C}, {a, b, c}, P, A)
P = {A → Ba | AbC,
B → Bab | ba | AcC,
C → ab | CB | c}
Pomocí algoritmu z přednášky zkonstruujte ke gramatice G ekvivalentní nelevorekurzivní gramatiku.
Uveďte, jaké uspořádání neterminálů jste zvolili při odstraňování nepřímé levé rekurze a rovněž
celý postup převodu. Nezapomeňte stručně zdůvodnit, proč gramatika G splňuje vstupní podmínku
uvedeného algoritmu.
Následně gramatiku převeďte do Greibachové normální formy. Použijte algoritmus z přednášky
(nebo dokažte, že je vaše gramatika v GNF ekvivalentní G).
K odstranění levé rekurze v gramatice G využijeme algoritmu z přednášky.
Gramatika splňuje vstupní podmínku algoritmu, protože:
• neobsahuje ε-pravidla,
• je necyklická,
• neobsahuje nepoužitelné symboly.
Jde tedy o gramatiku vlastní.
Zvolíme výchozí uspořádání neterminálů A B C. Jejich závislosti znázorňuje následující graf
(pro všechna pravidla tvaru X → Y α, kde X, Y ∈ {A, B, C} a α ∈ {A, B, C, a, b, c}∗ existuje hrana
X → Y ).
A
B
C
Využitím algoritmu z přednášky postupně odstraníme všechny zpětné hrany (případná nepřímá
rekurze) a cykly (přímá rekurze). Nejdříve odstraníme přímou rekurzi u neterminálu A přidáním
nového neterminálu A . Po jejím odstranění vypadají pravidla následovně:
P1 = {A → Ba | BaA ,
A → bC | bCA ,
B → Bab | ba | AcC,
C → ab | CB | c}
Dále odstraníme zpětnou hranu B → A, která způsobuje nepřímou levou rekurzi.
P2 = {A → Ba | BaA ,
A → bC | bCA ,
B → Bab | ba | BacC | BaA cC,
C → ab | CB | c}
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB102 úkol 10, příklad 1 Odevzdání: 3. 12. 2018
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
Poté odstraníme přímou levou rekurzi B → B stejným způsobem jako u A.
P3 = {A → Ba | BaA ,
A → bC | bCA ,
B → ba | baB ,
B → ab | acC | aA cC | abB | acCB | aA cCB ,
C → ab | CB | c}
Zbývá nám odstranit přímou levou rekurzi u C. Vzniká výsledná nelevorekurzivní gramatika:
G = ({A, B, C, A , B , C }, {a, b, c}, P , A)
P = {A → Ba | BaA ,
A → bC | bCA ,
B → ba | baB ,
B → ab | acC | aA cC | abB | acCB | aA cCB ,
C → ab | c | abC | cC ,
C → B | BC }
Pro převod do Greibachové normální formy volíme uspořádání A C B A B C podle
následujícího grafu.
A
B
C A B C
Po transformaci pravidel do GNF podle algoritmu z přednášky (substitucí v pravidlech C → Bα
a A → Bα a nakonec zavedením nových neterminálů a , b , c ) získáváme gramatiku G :
G = ({A, A , B, B , C, C , a , b , c }, {a, b, c}, P , S)
P = {A → ba a | ba B a | ba a A | ba Ba A ,
A → bC | bCA ,
B → ba | ba B ,
B → ab | ac C | aA c C | ab B | ac CB | aA c CB ,
C → ab | c | ab C | cC ,
C → ba | ba B | ba C | ba B C
a → a,
b → b,
c → c}
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.