25.1.2010 IB102 Automaty a gramatiky 120 minut Jméno: Místnost: Souřadnice: r. n r. n r. n r. n r. n r. n r. n r. n r. n r. n Vl/Sv l_T J_l l_L 1 UCO Lľ J_l Ľ" J_l L" 'J Lľ J_l Ľ" J_l L" 'J L" J_l O O du Lľ J_l l_L '_l L" 'J Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Navrhněte zásobníkový automat M. akceptující jazyk Přiklad 1 40 bodů L = {cŕb2jckď I i, j, k > 0, j > k}. Uveďte, jakým způsobem navržený automat akceptuje. Oblast strojově snímatelných informací, nezasahujte. 25.1.2010 IB102 Automaty a gramatiky 120 minut Jméno: Místnost: Souřadnice: E r, n r. n r. n r, n r. n r. n r. .n r. .n r. n r. n Vl/Sv l_T J_l ^H^tt UCO Lľ J_l Ľ" J_l L" 'J Lľ J_l Ľ" J_l L" 'J L" J_l OO&U Lľ J_l l_L '_l L" 'J Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Uvažme následující pravou kongruenci ~ na slovech nad abecedou X = {a, b}: Příklad 2 35 bodů de f u ~ v -<==> #a(w) mod 4 = #a(v) mod 4 (a) Určete index ~. (b) Najděte jazyk L nad X takový, že <~l = ~. (c) Najděte jazyk L, který je sjednocením některých tříd rozkladu X* podle ~, ale přitom ~L ^ ^. Oblast strojově snímatelných informací, nezasahujte. 25.1.2010 IB102 Automaty a gramatiky 120 minut Jméno: Místnost: Souřadnice: 3 r. n r. n r. n r, .n r. .n r. n r. .n r. n r. n r. n Vl/Sv l_T J_l ^H^J UCO Lľ J_l Ľ" J_l L" 'J Lľ J_l Ľ" J_l L" 'J L" J_l OO&U Lľ J_l l_L '_l L" 'J Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Je dána gramatika Q = ({S, A, B}, {a, b, c}, P, S), kde Příklad 3 35 bodů P = { S -»■ AaA \ ab \ B A -»■ BaBb \ c \ B B ^ Bc | S }. Převeďte gramatiku ŕ/ na ekvivalentní gramatiku v CNF. Pokud nepoužijete algoritmus z přednášky, zdůvodněte ekvivalenci výsledné gramatiky s gramatikou ze zadání. Oblast strojově snímatelných informací, nezasahujte. 25.1.2010 IB102 Automaty a gramatiky 120 minut Jméno: Místnost: Souřadnice: H r, n r. n r. n r, n r. n r. n r. .n r. n r. n r. n Vl/Sv l_T J_l l_L 1 UCO Lľ J_l Ľ" J_l L" 'J Lľ J_l Ľ" J_l L" 'J L" J_l OOďtJ Lľ J_l l_L '_l L" 'J Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Zformulujte algoritmus, který k danému nedeterministickému konečnému au- Přiklad 4 tomatu M = (Q,T:,ö,qo,F) zkonstruuje jazykově ekvivalentní deterministický 40 bodů automat bez nedosažitelných stavů a s totální přechodovou funkcí. (Nezapomeňte přesně popsat výstupní automat.) Oblast strojově snímatelných informací, nezasahujte. 25.1.2010 IB102 Automaty a gramatiky 120 minut Jméno: Místnost: Souřadnice: B r, n r. n r. n r, n r. n r. n r. .n r. n r. n r. n Vl/Sv l_T J_l ^H^J UCO Lľ J_l Ľ" J_l L" 'J Lľ J_l Ľ" J_l L" 'J L" J_l OOďtJ Lľ J_l l_L '_l L" 'J Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Rozhodněte, zda existují následující gramatiky. V kladném případě uveďte příklad Příklad 5 takové gramatiky, v záporném důkaz její neexistence. 15+15 bodů (a) Bezkontextová gramatika bez jednoduchých pravidel a bez e-pravidel, která je cyklická. (b) Bezkontextová gramatika, která má vlastnost sebevložení, ale generuje regulární jazyk. Oblast strojově snímatelných informací, nezasahujte. 25.1.2010 IB102 Automaty a gramatiky 120 minut Jméno: Místnost: Souřadnice: E r, n r. n r. n r, n r. n r. n r. .n r. n r. n r. n Vl/Sv l_T J_l ^H^J UCO Lľ J_l Ľ" J_l L" 'J Lľ J_l Ľ" J_l L" 'J L" J_l OOďtJ Lľ J_l l_L '_l L" 'J Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Příklad 6 (a) Definujte Turingův stroj (včetně podmínky kladené na přechodovou funkci). 35+5+5 bodů (b) Jak se nazývá třída jazyků akceptovaných Turingovými stroji? (c) Jak se nazývá třída jazyků akceptovaných úplnými Turingovými stroji? Oblast strojově snímatelných informací, nezasahujte. Datum: IB102 Automaty a gramatiky 120 minut Jméno: Místnost: Souřadnice: r. n r. n r, n r. n r. n r. n r. n r. n r. n r. n r. n r. n h%Sv Lľ J_l l_L 'J UCO Lľ J_l Ľ" J_l L" 'J L" J_l Ľ" J_l L" 'J L" J_l OO&U Lľ J_l l_L '_l L" 'J Oblast strojově snímatelných informací. Své UČO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte. Oblast strojově snímatelných informací, nezasahujte.