9.1.2014
IB102    Automaty, gramatiky a složitost
120 minut
Jméno: Místnost: Souřadnice:
říSÍ l       U    l       I UČO C       j    l l        j    l        j    l l        j    l        j boďl/
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 IE3H5E1B3
O každém z následujících jazyků rozhodněte, zda je bezkontextový. Svá tvrzení Přiklad 1 dokažte. (Pro důkaz, že jazyk je bezkontextový, stačí napsat odpovídající gramatiku 35 bodů
nebo automat.)
(a) {an(bc2)n | n > 0}
(b) {an(bcn)2 | n > 0}
Oblast strojově snímatelných informací, nezasahujte.
9.1.2014
IB102    Automaty, gramatiky a složitost
120 minut
Jméno:
Místnost:
Souřadnice:
list
E
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.
U IE3H5E1B3
Je dán automat A:
Příklad 2
20 bodů
Napište regulární výraz E popisující jazyk L(A).
(Pokud použijete standardní algoritmus a zakreslíte všechny jeho mezivýsledky, nemusíte dokazovat rovnost L{E) = L(A). V opačném případě rovnost dokažte.)
Oblast strojově snímatelných informací, nezasahujte.
9.1.2014
IB102    Automaty, gramatiky a složitost
120 minut
Jméno: Místnost: Souřadnice:
3
říSÍ l       U    —J UČO C       j    l l        j    l        j    l l        j    l        j boďl/
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 IE3H5E1B3
Je dána gramatika Q = ({S, A, B}, {a, b}, P, S), kde Příklad 3
13+10 bodů
P = { S -+ ABa | Ab A —> aBB | aa B -> Ab      | b | e }.
(a) Zkonstruujte PDA A 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 aaabba.
Oblast strojově snímatelných informací, nezasahujte.
9.1.2014
IB102    Automaty, gramatiky a složitost
120 minut
Jméno:
Místnost:
Souřadnice:
list
H
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.
U IE3H5E1B3
Rozhodněte, zda platí následující implikace. Svá tvrzení zdůvodněte.
(a) A je bezkontextový a B není regulární A\ B není regulární
(b) A je deterministický bezkontextový a B je bezkontextový
co —{A \ B) je bezkontextový
Příklad 4
10+10+10 bodů
(c) A je regulární a i? G N P
A i? je rekurzivní
Oblast strojově snímatelných informací, nezasahujte.
9.1.2014
IB102    Automaty, gramatiky a složitost
120 minut
Jméno: Místnost: Souřadnice:
B
říSÍ l       U    —J UČO C       j    l l        j    l        j    l l        j    l        j boďl/
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 IE3H5E1B3
Definujte jednopáskový deterministický Turingův stroj (včetně podmínky kladené Přiklad 5 na přechodovou funkci). 22 bodů
Oblast strojově snímatelných informací, nezasahujte.
9.1.2014
IB102    Automaty, gramatiky a složitost
120 minut
Jméno: Místnost: Souřadnice:
E
říSÍ l       U    LJ UČO C       j    l l        j    l        j    l l        j    l        j boďl/
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 IE3H5E1B3
Příklad 6
(a) Zformulujte Savitchovu větu. 10+10 bodů
(b) Jaký vztah inkluze (C nebo D) je mezi třídami SPACE(10n8) a NTIME(42ra3)? Odpověď zdůvodněte. (Není třeba zdůvodňovat, proč f £ 0{g)).
Oblast strojově snímatelných informací, nezasahujte.
Datum: IB102    Automaty, gramatiky a složitost 120 minut
Jméno: Místnost: Souřadnice:
list   c u ľ  j nčo   ľ -j ľ u ľ -j ľ -j ll u ľ -j ľ -j body
Oblast strojově snímatelných informací. Své U CO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
D IE3H5E1B3
Oblast strojově snímatelných informací, nezasahujte.