IB102 úkol 6, příklad 3 Odevzdání: 4. 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.
3. [2 body] Nechť Σ = {a, b, c}. Napište algoritmus, který pro zadaný deterministický konečný
automat A = (Q, Σ, δ, q0, F) spočítá maximální množinu všech stavů takových, že z každého z nich
lze akceptovat alespoň jedno slovo se suffixem ab. Výstupem algoritmu tedy bude množina stavů
P = q ∈ Q | ∃x ∈ Σ∗
, δ(q, xab) ∈ F .
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.