IB102 – úkol 10, příklad 2 – řešení Odevzdání: 3. 12. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [1 bod] Převeďte gramatiku G, která je ve tvaru bez levé rekurze, do Greibachové
normální formy. Použijte algoritmus z přednášky (nebo dokažte, že je vaše gramatika v
GNF ekvivalentní G).
G = ({W, X, Y, Z}, {a, b, c}, P, W)
P = { W → bX | Y W,
X → aXaX | ZZ,
Y → a | cY a,
Z → bZ | Y cY | WW }
Schematický nákres pro zjednodušení volby uspořádání:
X Z W Y
Vhodné uspořádání pro algoritmus převodu do GNF je tedy X Z W Y .
• i = 3, Ai = W
– j = 4, Aj = Y : W → bX | aW | cY aW
• i = 2, Ai = Z
– j = 4, Aj = Y : Z → bZ | acY | cY acY | WW
– j = 3, Aj = W: Z → bZ | acY | cY acY | bXW | aWW | cY aWW
• i = 1, Ai = X
– j = 4, Aj = Y : X → aXaX | ZZ
– j = 3, Aj = W: X → aXaX | ZZ
– j = 2, Aj = Z: X → aXaX | bZZ | acY Z | cY acY Z | bXWZ | aWWZ |
cY aWWZ
Nyní zbývá jen nahradit terminály za neterminály. Výsledná gramatika G v GNF:
G = ({W, X, Y, Z, A, C}, {a, b, c}, P, W)
P = { W → bX | aW | cY AW,
X → aXAX | bZZ | aCY Z | cY ACY Z | bXWZ | aWWZ | cY AWWZ,
Y → a | cY A,
Z → bZ | aCY | cY ACY | bXW | aWW | cY AWW,
A → a,
C → c }