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ívaatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
DíiaaHBBnsg
Navrhněte bezkontextovou gramatiku Q v Greibachové normální formě generující        Příklad  1 jazyk                                                                                                                                  40 bodů
L = {aib2^cib2k \i,j,k>0}.
(Rovnost L = L (Q) není třeba dokazovat.)
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
Uvažme následující relace na slovech nad abecedou E = {a, b}. U každé relace        Přiklad 2 určete, zda se jedná o pravou kongruenci. Pokud rozhodnete, že se o pravou             33 bodů
kongruenci nejedná, dokažte to. V opačném případě určete index ekvivalence a popište jednotlivé třídy ekvivalence.
(aj u ~ v   <í=^    |it| < |u|
(b) u ~ w    <í=^   u,v G {a}.E+   nebo  u,v £ {b}.T,+   nebo  u = v
Oblast strojově snímatelných informací, 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
20+15 bodů
= { S  ->■  AaB	\  Bb  \  e
A  ->■ cAb	\   aS   \   Ab
B  -> Bb	1   bA  }.
(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 bcabb.
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ívaatelný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é bezkontextové gramatice zkonstruuje jazykově     Přiklad 4 ekvivalentní gramatiku bez e-pravidel.                                                                               40 bodů
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ívaatelných informací. Své UCO vyplňte zleva dle přiloženého vzoru číslic. Jinak do této oblasti nezasahujte.
DíiaaHBBnsg
Nechť L je bezkontextový jazyk. Dokažte nebo vyvraťte následující implikace:           Přiklad 5
16+16 bodů
(a) L má vlastnost sebevložení  =^  L je nekonečný
(b) L je nekonečný   =^-  L má vlastnost sebevložení
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ť A = (Q,T,,ô,qo,F) je deterministický konečný automat rozpoznávající        Přiklad 6 jazyk L. Označme n =  card (Q). Dokažte, že L je nekonečný, právě když A             40 bodů
akceptuje alespoň jedno slovo w s vlastností n < \w\ < In.
Oblast strojově snímatelných informací, nezasahujte.