IB102 úkol 9, příklad 2 Odevzdání: 25. 11. 2019
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.
2. [2 body]
a) Uvažte následující gramatiku G1:
G1 = ({S, X, Y, Z}, {a, b, c}, P, S),
P = { S → Y Z | aXZa,
X → Y X | bY | aY Z,
Y → ε | c | Y Z,
Z → a | Xb | ε | c}.
Pomocí algoritmů z přednášky převeďte gramatiku G1 na ekvivalentní gramatiku bez ε-pravidel a
následně z takto vzniklé gramatiky odstraňte jednoduchá pravidla. Do řešení uveďte celý postup
převodu, zejména:
1. ke gramatice G1 ekvivalentní gramatiku G1 bez ε-pravidel (nezapomeňte uvést množinu Nε
obsahující všechny neterminály, které se dají přepsat na ε),
2. ke gramatice G1 ekvivalentní gramatiku G1 bez ε-pravidel a jednoduchých pravidel (uveďte
množiny NA, t.j. množiny všech neterminálů, na které se může A ∈ N přepsat pomocí jednoduchých
pravidel).
b) Uvažte následující gramatiku G2:
G2 = ({S, A, B, C, D, E}, {a, b, c}, P, S),
P = { S → Aa | a | Eb | abbc | aDD,
A → Aab | b | SEE | baD,
B → DaS | BaaC | a,
C → Da | a | bB | Db | SaD,
D → Da | DBc | bDb | DEaD,
E → Aa | a | bca}.
Pomocí algoritmů z přednášky převeďte gramatiku G2 na ekvivalentní vlastní gramatiku a
následně na gramatiku v Chomského normální formě. Do řešení uveďte celý postup převodu,
zejména:
1. ke gramatice G2 ekvivalentní vlastní gramatiku G2,
2. ke gramatice G2 ekvivalentní gramatiku G2 v Chomského normální formě (CNF).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.