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
Navrhněte zásobníkový automat akceptující jazyk                                                    Přiklad  1
40 bodů
L = {w.cn | w G {a, 6}*, n > 0, #a{w) > n}.
Uveďte, jakým způsobem navržený automat akceptuje.
Oblast strojově snímatelných informaci, 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
33 bodů
L = {aíb'ck | i,j,k >0, i^A;}
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 bezkontextová gramatika G = {{S, A, B}, {a, b, c}, P, S), kde                         Přiklad 3
45 bodů
p = { S  ->■  Ac
A  —>  Ba |   Sa B  -+  SS |   b  }.
Převeďte gramatiku Q do Greibachové normálni formy. Použijete-li algoritmus z přednášky, uveďte zvolené uspořádání neterminálů. V ostatních případech dokažte, že výsledná gramatika je jazykově ekvivalentní gramatice ze zadání.
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é bezkontextové gramatice Q = (N,T,,P,S)        Přiklad 4 bez £-pravidel zkonstruuje jazykově ekvivalentní gramatiku bez jednoduchých             40 bodů
pravidel a bez e-pravidel. (Nezapomeňte přesně popsat výstupní gramatiku.)
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
Dokažte nebo vyvraťte následující tvrzení:                                                               Přiklad  5
16+16 bodů
(a)   Každá redukovaná bezkontextová gramatika generuje neprázdný jazyk.
(b)   Třída regulárních jazyků je uzavřená na průnik s bezkontextovým jazykem.
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
Příklad 6
(a) Definujte pojem gramatika.                                                                                20+10 bodů
(b) Definujte, kdy se jazyk nazývá rekursivně spočetný.
Oblast strojově snímatelných informaci, nezasahujte.