IB102 – úkol 6, příklad 3 – řešení Odevzdání: 16. 11. 2015
Vypracoval(a): UČO:
Skupina:
3. [2 body] Uvažte následující gramatiku G:
G = ({S, A, B, C, D}, {a, b}, P, S),
P = { S → BaC | SbbA | ε,
A → a | BA | ε,
B → A | bbCS | a,
C → bDC | aC,
D → C | a}.
Pomocí algoritmů z přednášky převeďte gramatiku G na ekvivalentní gramatiku v Chomského
normální formě. Do řešení uveďte celý postup převodu, zejména následující mezi-
výsledky:
a) ke gramatice G ekvivalentní gramatiku G1 bez ε-pravidel (nezapomeňte uvést množinu
Nε obsahující všechny neterminály, které se dají přepsat na ε),
b) ke gramatice G1 ekvivalentní gramatiku G2 bez ε-pravidel a jednoduchých pravidel
(uveďte množiny NX, t.j. množiny všech neterminálů, na které se může X ∈ N pře-
psat),
c) ke gramatice G2 ekvivalentní vlastní gramatiku G3,
d) ke gramatice G3 ekvivalentní gramatiku G4 v Chomského normální formě (CNF).
Prvním krokem je odstranění ε-pravidel z gramatiky G. Množina neterminálů, které je
možné přepsat na ε, je Nε = {A, B, S}. Výsledkem algoritmu z přednášky (5. přednáška,
slajd 21) je poté gramatika
G1 = ({S , S, A, B, C, D}, {a, b}, P1, S ),
P1 = { S → ε | S,
S → BaC | aC | SbbA | bbA | Sbb | bb,
A → a | BA | B | A,
B → A | bbCS | bbC | a,
C → bDC | aC,
D → C | a}.
Druhým krokem je odstranění jednoduchých pravidel. Algoritmus z přednášky můžeme
použít, protože gramatika G1 již neobsahuje ε-pravidla. Pro všechny neterminály X ∈ N
IB102 – úkol 6, příklad 3 – řešení Odevzdání: 16. 11. 2015
Vypracoval(a): UČO:
Skupina:
jsou množiny neterminálů, na něž lze neterminál X přepsat, následující:
NS = {S , S},
NS = {S},
NA = {A, B},
NB = {A, B},
NC = {C},
ND = {C, D}.
Výsledkem algoritmu z přednášky (5. přednáška, slajd 25) je poté gramatika
G2 = ({S , S, A, B, C, D}, {a, b}, P2, S ),
P2 = { S → ε | BaC | aC | SbbA | bbA | Sbb | bb,
S → BaC | aC | SbbA | bbA | Sbb | bb,
A → a | BA | bbCS | bbC,
B → a | BA | bbCS | bbC,
C → bDC | aC,
D → bDC | aC | a}.
Třetím krokem je odstranění nenormovaných neterminálů. Iterativně přidáváme do Ni
neterminály, které lze v i krocích přepsat na řetězec terminálů. Výsledkem je množina:
Ne = {S , S, A, B, D}.
Výsledkem algoritmu z přednášky (5. přednáška, slajd 11) je poté gramatika
G3a = ({S , S, A, B, D}, {a, b}, P3a, S ),
P3a = { S → ε | SbbA | bbA | Sbb | bb,
S → SbbA | bbA | Sbb | bb,
A → a | BA,
B → a | BA,
D → a}.
Čtvrtým krokem je odstranění nedosažitelných symbolů. Podle algoritmu z přednášky
(5. přednáška, slajd 15) nejprve postupně zkonstruujeme následující množiny Vi
V0 = {S },
V1 = {S , S, b, A},
V2 = {S , S, a, b, A, B},
V3 = V2
IB102 – úkol 6, příklad 3 – řešení Odevzdání: 16. 11. 2015
Vypracoval(a): UČO:
Skupina:
a výstupem algoritmu je poté gramatika
G3 = ({S , S, A, B}, {a, b}, P3, S ),
P3 = { S → ε | SbbA | bbA | Sbb | bb,
S → SbbA | bbA | Sbb | bb,
A → a | BA,
B → a | BA}.
Gramatika G3 neobsahuje jednoduchá ani ε-pravidla, a tudíž je také necyklická. Navíc
neobsahuje ani nepoužitelné symboly, a tedy se jedná o vlastní gramatiku.
Posledním krokem je převod gramatiky G3 do Chomského normální formy podle algoritmu
z přednášky (6. přednáška, slajd 4). Tento algoritmus smíme použít, protože
gramatika G3 je vlastní a bez jednoduchých pravidel.
Výsledkem tohoto algoritmu je gramatika
G4 = ({S , S, A, B, b b A , b A , b b , a , b }, {a, b}, P4, S ),
P4 = { S → ε | S b b A | b b A | S b b | b b ,
S → S b b A | b b A | S b b | b b ,
A → a | BA,
B → a | BA,
b b A → b b A ,
b A → b A,
b b → b b ,
a → a,
b → b}.