PV030 – Textové informační systémy
2013
Úkoly nahrazující půlsemestrovou písemku
A) Mějme množinu vzorků P={tis, ti, iti}.
a) Vytvořte NKA pro vyhledávání P.
b) Vytvořte DKA příslušný tomuto NKA a zminimalizujte jej. Nakreslete přechodové diagramy
obou automatů (DKA a minimálního DKA) a popište postup minimalizace.
c) Srovnejte s výsledkem vyhledávacího stroje AC.
d) Řešte úlohu také algoritmem přímé konstrukce DKA (derivováním) a diskutujte, zda výsledkem
jsou izomorfní automaty.
B) Mějme regulární výraz R = 1(0 + 1∗
02) nad abecedou A = {0, 1, 2}.
a) Sestrojte DKA pro protisměrné vyhledávání R (Bucziłowski) a spočtěte chybovou funkci.
Nakreslete přechodový diagram tohoto automatu včetně vizualizace chybové funkce.
RR = (0 + 201∗)1
b) Zapište výsledný automat jako 2DKAS a trasujte vyhledávání v textu 11201012102.
C) Dokažte:
h dV
dx = {y : xy ∈ h(V )}
D) Najděte takový příklad řetězců X a Y , že platí zároveň R(X, Y ) = 5, DIR(X, Y ) = 4 i
DIRT(X, Y ) = 3, nebo dokažte neexistenci takových řetězců.
1