BI-AAG_quiz05

[NEBODOVANÁ OTÁZKA]

Kterou část látky bys po kvízu chtěl(a)/potřeboval(a) zopakovat?

• Determinizace NKA

• Minimalizace DKA

• Odstranění ε-přechodů z NKA

• Konečný automat pro iteraci jazyka

• Konečný automat pro zřetězení jazyků

Mějme NKA s více počátečními stavy, který obsahuje ε-přechody. Jakou posloupnost algoritmů na něj musíme aplikovat, abychom ho převedli na ekvivalentní minimální DKA?

• Odstranění více počátečních stavů, odstranění ε-přechodů, determinizace, minimalizace

• Odstranění ε-přechodů, odstranění zbytečných a počátečních stavů, determinizace, minimalizace

• Odstranění ε-přechodů a více počátečních stavů, determinizace, odstranění zbytečných stavů, sloučení ekvivalentních stavů

• Kouknu a vidim

Z jakých dílčích kroků se skládá algoritmus pro minimalizaci DKA?

• Odstranění zbytečných a nedostžitelných stavů, sloučení ekvivalentních stavů

• Odstranění více počátečních stavů, odstranění nedosažitelných a zbytečných stavů

• Pouze sloučení ekvivalentních stavů

V jakém čase pracuje DKA? (tj. v jakém čase dokáže DKA rozhodnout, zda slovo délky n patří do jazyka přijímaného tímto DKA?)

• O(n)

• O(n^2)

• O(2^n)

• O(1)

Lze algoritmicky rozhodnout, zda dvě regulární gramatiky generují stejný jazyk? Pokud ano, v jakém čase vůči počtu jejich neterminálů?

• Ano, lze to v kvadratickém čase

• Ano, lze to v lineárním čase

• Ano, lze to v exponenciálním čase

• Tento problém obecně rozhodnout nelze