3.2.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 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. O každém z následujících jazyků rozhodněte, zda je hezkontextový. Svá tvrzení Přiklad 1 dokažte. (Pro důkaz, že jazyk je hezkontextový, stačí napsat odpovídající gramatiku 50 bodů nebo automat.) (a) L1 = {we {a,b,c}* | #a(w) < #c(w) A #b(w) < #c(w)} (b) L2 = {we {a, b, c}* | #0(«;) = 2 • #b(w)} Oblast strojově snímatelných informací, nezasahujte. 3.2.2010 IB102 Automaty a gramatiky 120 minut Jméno: Místnost: Souřadnice: list E r, _n r. _n r .n r, .n r. _n r .n r .n r. .n r. n r .n UCO body 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. DíiaaHBEnsg K zadanému konečnému automatu zkonstruujte ekvivalentní Přiklad 2 deterministický konečný automat s totální přechodovou funkcí. 30 bodů (Pokud nepoužijete standardní algoritmus, dokažte ekvivalenci obou automatů.) c d ->■ 1 {5} {4} 2 {4} {2,3} ^3 {1} {1,3} ^4 0 {1} 5 {3,5} {1,5} ^6 {2,3} {1,4,6} Oblast strojově snímatelných informací, nezasahujte. 3.2.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}, P, S), kde Příklad 3 20+15 bodů P = { S ->■ aAA | Bb A -> aB j bb B ^ Bb | bS | e }. (a) Zkonstruujte PDA .4 pro nedeterministickou syntaktickou analýzu shora dolů. Uveďte způsob akceptování. (b) Zapište akceptující výpočet automatu A nad slovem aabbb. Oblast strojově snímatelných informací, nezasahujte. 3.2.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é bezkontextové gramatice Q = (N, Y*, P, S) Přiklad 4 bez e-pravidel zkonstruuje jazykové ekvivalentní gramatiku bez jednoduchých 40 bodů pravidel a bez e-pravidel. (Nezapomeňte presné popsat výstupní gramatiku.) Oblast strojové snímatelných informací, nezasahujte. 3.2.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, která je cyklická. (b) Frázová gramatika, která není kontextová, ale generuje konečný jazyk. Oblast strojově snímatelných informací, nezasahujte. 3.2.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&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. Příklad 6 (a) Zformulujte Myhill-Nerodovu větu. 25+15 bodů (b) Nechť M = (Q,T,,T,ö,q0,Z0,F) je PDA. Napište podmínky, které musí platit, aby byl zásobníkový automat deterministický. 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.