IB005 úkol 8, příklad 2 Odevzdání: 19. 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.
2. [0,5 bodu] Nechť Σ = {a, b, c}. Napište algoritmus, který pro zadanou bezkontextovou gramatiku
G = (N, Σ, P, S) spočítá množinu všech neterminálů takových, že z každého z nich lze pro
libovolné n vygenerovat slovo, které obsahuje alespoň n symbolů a. Výstupem algoritmu tedy bude
množina neterminálů
Na = {X ∈ N | ∀n∃w ∈ Σ∗
.X ⇒∗
w ∧ #a(w) ≥ n} .
Příklad gramatiky:
G = ({D, A, B, E, F, G}, {a, b, c}, P, D)
P = {D → DAab | ε, A → ε | bc | BB,
B → aBc, E → bF | ca,
F → Ga | b, G → bF}
Korektní výstup algoritmu pro ni: Na = {D, E, F, G}.
Popište princip fungování vašeho algoritmu a dokažte, že je tento algoritmus konvergentní (vždy
skončí). Můžete využívat libovolné algoritmy z přednášky, musíte na to však upozornit v textu.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.