24.lf.2006 IB102 Automaty a gramatiky Cas: 90 minut Jméno: Místnost: Souřadnice: rr n rr m rr ,n rr ,n r, ,n rr ,n rr ,n r, ,n rr ,n r, ,n rr ,n r, ,n IZS* Ľ" J Ľ" 1 UCO Ľ" J Ľ" 'J Ľ JJ l_ľ J Ľ" 'J Ľ JJ l_ľ J OOďy C J Ľ" J Ľ 'J Oblast strojově smmatelných informací. Své UCO vyplňte zleva Ml 1 ^ ^ U [ľ CT n D dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. LI 1 Li Z3 H -3 Q L I Q _J Příklad 1 Napište definici deterministického konečného automatu a rozšířené přechodové funkce. 1JViau -1- 10 bodů Určete, kolik slov má jazyk L3 \ L, kde L = {a, aa, aaa}. ťrlKiaCL Z 5 bodů Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 24.11.2006 IB102 Automaty a gramatiky Cas: 90 minut Jméno: Místnost: Souřadnice: list L J E rr n rr ,~i r, ,~i rr ,n rr ,n r, ,n rr ,n UCO Oblast strojově smmatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. r, n rr n r, ,~i body ĺ j ĺ j ĺ j DilB3HBBnBa Najděte deterministický konečný automat rozpoznávající jazyk L = {w G {a,b,c}* j w obsahuje podslovo babaab}. Příklad 3 10 bodů Nechť L,R jsou jazyky nad abecedou S = {a, b}. Rozhodněte, zda platí následující implikace a svá rozhodnutí zdůvodněte: (a) L a L.R jsou regulární =^- R je regulární (b) L U R není regulární =^> L nebo R není regulární Příklad 4 15 bodů Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 24.11.2006 IB102 Automaty a gramatiky Cas: 90 minut Jméno: Místnost: Souřadnice: 3 rr n rr ,~i r, ,n rr ,n rr ,n r, ,n rr n r, n rr ,n r, ,~i IZS* Ľ" J ^HM UCO Ľ" J Ľ" 'J Ľ 'J l_ľ J Ľ" 'J Ľ 'J l_ľ J OOďy C J Ľ" J Ľ JJ Oblast strojově smmatelných informací. Své UCO vyplňte zleva Ml 1 ^ ^ U [ľ CT n D dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. LI 1 Li Z3 H -3 Q L I Q _J Rozhodněte, zda je jazyk L = {a}*.{w G {b, c}* \ #b{w) = #c{w)} regulární. ťrlKiaCL O Své tvrzení dokažte. u Doau Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 24.11.2006 IB102 Automaty a gramatiky Cas: 90 minut Jméno: Místnost: Souřadnice: list L J H rr n rr ,~i r, ,~i rr ,n rr ,n r, ,n rr ,n UCO r, ,n rr n r, ,n 6ody L- j ĺ j L- j Oblast strojově smmatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. DilB3HBBnBa K danému konečnému automatu A sestrojte ekvivalentní (nedeterministický) konečný automat bez e-kroků. A a b £ ->■ 1 {2} {4} {3,5} 2 {2,3} 0 {5} <- 3 0 {1,4,5} 0 <- 4 {4} {2} 0 5 0 {3,4} {2} Příklad 6 20 bodů Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 24.11.2006 IB102 Automaty a gramatiky Cas: 90 minut Jméno: Místnost: Souřadnice: 5 rr n rr ,~i r, ,n rr ,n rr ,n r, ,n rr n r, n rr ,n r, ,~i IZS* Ľ" J ^HM UCO Ľ" J Ľ" 'J Ľ 'J l_ľ J Ľ" 'J Ľ 'J l_ľ J OOďy C J Ľ" J Ľ JJ Oblast strojově snímatelných informací. Své UCO vyplňte zleva r n 1 I] ^ U Cľ Ľ "1 Cľl □ dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. U 1 CZ Z3 H -3 Q L I Q _J Uvažujte následující relace na slovech nad abecedou E = {a, b}. U každé relace určete, ťrlKiacL / zda se jedná o pravou kongruenci. Pokud rozhodnete, že se o pravou kongruenci ne- u bodu jedná, dokažte to. V opačném případě určete index relace a popište jednotlivé třídy ekvivalence. (a) u~v <Ě4 #a(u) = #a(v) + 1 (b) U~V <^ #a{u)=#a(v) de f (c) u ~ v <í=^ #a{u) i #a(f) jsou liché nebo u = v def (d) u ~ v -í=? #a{u) a #a(f) mají stejnou paritu Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu. 24.11.2006 IB102 Automaty a gramatiky Cas: 90 minut Jméno: Místnost: Souřadnice: rr n rr ,~i rr ,n rr ,n r, ,n rr ,n rr ,n r, ,n rr ,n r, ,n rr ,n r, ,n its* ľ jj ľ" 'j uco ľ jj ľ" 'j ľ jj ľ" jj ľ" 'j ľ jj ľ" jj ooďy c jj ll jj ľ jj Oblast strojově smmatelných informací. Své UCO vyplňte zleva Ml 1 ^ ^ U [ľ CT n D dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. LI 1 Li Z3 H 13 Q L I Q _J Oblast strojově snímatelných informací, nezasahujte. Řešení pište jen na tuto stranu.