13.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 bezkontextovou gramatiku Q v Greibachove normální formě generující Přiklad 1 jazyk 40 bodů L{G) = {aibjckd2j | i,j,k>0}. (Rovnost L = L (Q) není třeba dokazovat.) Oblast strojově snímatelných informací, nezasahujte. 13.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. Zkonstruujte regulární výrazy popisující následující jazyky: Příklad 2 36 bodů (a) L\ = {w G {0,1}* | w neobsahuje podslovo 11} (b) L2 = {w G {a, b, c}* I w obsahuje podslova aaa a abc} Oblast strojově snímatelných informací, nezasahujte. 13.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}, P, S), kde Příklad 3 20+15 bodů P = { S ->■ aAA | Bb A -> aB j bb B ^ Bb | bS | e }. (a) Zkonstruujte rozšířený PDA .4 pro nedeterministickou syntaktickou analýzu zdola nahoru. 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. 13.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&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. Napište algoritmus, který pro zadanou redukovanou bezkontextovou gramatiku Přiklad 4 Q = (N, S, P, S) a zadaný symbol a G X spočítá množinu M všech neterminálů, 40 bodů z kterých lze odvodit řetězec obsahující a, tj. M = {A G N I A =>* -ucm; pro nejaké u, v G S*}. Oblast strojově snímatelných informací, nezasahujte. 13.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 O O d y 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á vlastní gramatika s jediným neterminálem, která generuje nekonečný jazyk obsahující i slovo e. (b) Kontextová gramatika, která není bezkontextová, ale generuje regulární jazyk. Oblast strojově snímatelných informací, nezasahujte. 13.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, kdy má bezkontextová gramatika vlastnost sebevložení. 10+10+10+14 bodů (b) Nechť L je jazyk nad abecedou E. Definujte relaci ~l zvanou prefixová ekvivalence pro L. (c) Definujte, kdy je neterminál bezkontextová gramatiky levorekursivní (d) Napište 5 operací nad jazyky, na které je třída bezkontextových jazyků uzavřená. Dále napište 2 operace nad jazyky, na které třída bezkontextových jazyků není uzavřená. 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.