Jméno:                                                             Místnost:                      Souřadnice:
its t    ľ   jj ľ   i                       uco    ľ   jj ľ   'j ľ   'j ľ   jj ľ   'j ľ   'j u   jj      ooďy    ľ   jj ľ   'j ľ   jj
Oblast strojově snímatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
DíiaaHBBnsg
O každém z následujících jazyků rozhodněte, zda je bezkontextový. Svá tvrzení        Příklad  1 dokažte. (Pro důkaz, že jazyk je bezkontextový, stačí napsat odpovídající gramatiku             45 bodů
nebo automat.)
(a)  L^tfVďliJ^^O, i^j}
(b)   L2 = {a}*.{b}*.{c}*   \  {0*6*0* | i > 0}
Oblast strojově snímatelných informací, nezasahujte.
Jméno:                                                             Místnost:                      Souřadnice:
E
rr     n   rr     ,~i   rr     ,n   rr     ,n   rr     ,n   rr     ,n   rr     ,n                                  rr     ,n   rr     ,n   rr     ,n
ItS V        l_L        JJ     M^fc                     UCO        L"        JJ     L"        'J     Ľ      'J     U        JJ     L"        'J     Ľ      'J     L"        JJ           OOďy        L"        JJ     Ľ      'J     Ľ        JJ
Oblast strojově snímatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
DíiaaHBBnsg
Pomocí Myhill-Nerodovy věty dokažte, že jazyk                                                       Příklad  2
30 bodů
L = {b}.{ww | w G {a,b}*}
není regulární.
Oblast strojově snímatelných informaci, nezasahujte.
Jméno:                                                             Místnost:                      Souřadnice:
3
rr     n   rr     ,~i   rr     ,n   rr     ,n   rr     ,n   rr     ,n   rr     ,n                                  rr     ,n   rr     ,n   rr     ,n
ItS V        l_L        JJ     ^B^J                     UCO        L"        JJ     L"        'J     Ľ     'J     U        JJ     L"        'J     Ľ     'J     L"        JJ           OOďy        L"        JJ     Ľ     'J     Ľ        JJ
Oblast strojově snímatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
DíiaaHBBnsg
Je dána gramatika G = ({S, A, B}, {a, b, c}, P, S1), kde                                                 Příklad 3
22+18 bodů
= { S  ->■  AaB	\  Bb  \  e
A  ->■ cAb	\   bS   \   a
B  -+ bS	1   bc  }■
(a)   Zkonstruujte rozšířený PDA A pro nedeterministickou syntaktickou analýzu zdola nahoru. Uveďte způsob akceptování. Popište rozdíl mezi použitou a standardní notací.
(b)   Zapište akceptující výpočet automatu A nad slovem cbbbb.
Oblast strojově snímatelných informací, nezasahujte.
Jméno:                                                             Místnost:                      Souřadnice:
H
rr     n   rr     ,~i   rr     ,n   rr     ,n   rr     ,n   rr     ,n   rr     ,n                                  rr     ,n   rr     ,n   rr     ,n
its t    ľ   jj ľ   i                            uco    ľ   jj ľ   'j ľ   'j ľ   jj ľ   'j ľ   'j ľ   jj      ooďy    ľ   jj ľ   'j ľ   jj
Oblast strojově snímatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
DíiaaHBBnsg
Zformulujte algoritmus, který k danému nedeterministickému konečnému au-       Příklad 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.
Jméno:                                                             Místnost:                      Souřadnice:
5
rr     n   rr     ,~i   rr     ,n   rr     ,n   rr     ,n   rr     ,n   rr     ,n                                  rr     ,n   rr     ,n   rr     ,n
ItS V        l_L        JJ     ^B^J                     UCO        L"        JJ     L"        'J     Ľ     'J     U        JJ     L"        'J     Ľ     'J     L"        JJ           OOďy        L"        JJ     Ľ     'J     Ľ        JJ
Oblast strojově snímatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
DíiaaHBBnsg
Nechť L,R jsou jazyky nad abecedou {a, b}. Dokažte nebo vyvraťte následující        Přiklad 5 implikace:                                                                                                                   15+15 bodů
(a)   L a R jsou neregulární  =^-  L n co—i? není regulární
(b)   L a R jsou deterministické bezkontextové   =í>   L U co—i? je bezkontextový
Oblast strojově snímatelných informací, nezasahujte.
Jméno:                                                             Místnost:                      Souřadnice:
E
rr     n   rr     ,~i   rr     ,n   rr     ,n   rr     ,n   rr     ,n   rr     ,n                                  rr     ,n   rr     ,n   rr     ,n
ItS V        l_L        JJ     M^J                     UCO        L"        JJ     L"        'J     Ľ     'J     U        JJ     L"        'J     Ľ     'J     L"        JJ           OOďy        L"        JJ     Ľ     'J     Ľ        JJ
Oblast strojově snímatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
DíiaaHBBnsg
Nechť M = (Q, S, T, í, qQ, Z0,F) je PDA.                                                               Příklad 6
7+5+9+14 bodů
(a)   Napište typ funkce ô.
(b)   Definujte konfiguraci PDA.
(c)   Definujte relaci krok výpočtu ( | M   ).
(d)   Napište podmínky, které musí PDA splňovat, aby byl deterministický.
Oblast strojově snímatelných informací, nezasahujte.