IB005 úkol 9, příklad 1 Odevzdání: 25. 4. 2022 12:00
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. [0,5 bodu]
a) Uvažte následující gramatiku G1:
G1 = ({X, A, B, F}, {m, a, j}, P1, X),
P1 = { X → FF | Baj | jA | FaX,
A → FFA | AjAj | aj,
B → mAj | BaF | FX,
F → ε | FjA}.
Pomocí algoritmů z přednášky převeďte gramatiku G1 na jazykově 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 jazykově ekvivalentní gramatiku G
′
1 bez ε-pravidel (nezapomeňte uvést množinu
Nε obsahující všechny neterminály, které se dají přepsat na ε),
2. ke gramatice G
′
1 jazykově ekvivalentní gramatiku G
′′
1 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řepsat pomocí
jednoduchých pravidel).
b) Uvažte následující gramatiku G2:
G2 = ({K, M, O, I}, {t, u, r}, P2, K),
P2 = { K → OtrOK | OtOK | rtut,
M → Krt | KrIK | IM,
O → KrOK | tur | tOM,
I → trIK | MOK}.
Pomocí algoritmů z přednášky převeďte gramatiku G2 na jazykově 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 jazykově ekvivalentní vlastní gramatiku G
′
2,
2. ke gramatice G
′
2 jazykově ekvivalentní gramatiku G
′′
2 v Chomského normální formě (CNF).
Poznámka: Pokud píšete řešení v TEXu, před odevzdáním prosím odmažte zadání.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.