9.1.2007                                     IB102     Automaty a gramatiky                          Cas: 120 minut
Jméno:                                                             Místnost:                      Souřadnice:
rr     71   r,     a                                           rr     71   rr     ,n   r,     ,n   rr     71   rr     71   r,     71   rr     71                                  rr     71   r,     71   r,     ,n
its t    ľ   jj ľ   1                 uco    ľ   jj ll   'j ľ   jj ll   jj ll   'j ľ   jj ll   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.
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             60 bodů
nebo automat.)
(a)   Lx = {anbncmdm \ m,n > 0}
(b)   L2 = {anbmcndm I m,n > 0}
(c)   L3 = {anbmcmdn \ m, n > 0}
Oblast strojově snímatelných informací, nezasahujte.
9.1.2007                                     IB102     Automaty a gramatiky                          Cas: 120 minut
Jméno:                                                             Místnost:                      Souřadnice:
E
.p   rr     ,-i   r,     ,n   rr     71   rr     ,n   r,     ,n   rr     ri                                  rr     71   r,     ,~i   r,     71
its t    ľ   jj k^ta                            uco    ľ   jj ll   'j ľ   jj ll   jj ll   'j ľ   jj ll   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.
Popište všechny jazyky L, pro které platí, že jazyk L* má stejně slov jako L.        Přiklad  2 Zdůvodněte, že popsané jazyky mají uvedenou vlastnost, i to, že ostatní jazyky             25 bodů
uvedenou vlastnost nemají.
Oblast strojově snímatelných informací, nezasahujte.
9.1.2007                                     IB102     Automaty a gramatiky                          Cas: 120 minut
Jméno:
Místnost:
Souřadnice:
list    L        J
3
.p   rr     ,n   r,     ,n   n.     71   rr     ,n   r,     ,n   rr     ri
,n   r,     ,~i   r,     ,n
uco    ľ   jj ľ"   'j ľ   jj ľ"   jj ľ"   'j ľ   jj ľ"   jj      ooďy    ľ   jj ľ   'j ľ   jj
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ílEaHBBHBg
Je dán automat A:
Příklad 3 30 bodů
Napište regulární výraz E popisující jazyk L(A).
(Rovnost L(E)  = L (A)  nemusíte dokazovat, pokud použijete standardní algoritmus a zakreslíte
všechny jeho mezivýsledky.)
Oblast strojově snímatelných informací, nezasahujte.
9.1.2007                                     IB102     Automaty a gramatiky                          Cas: 120 minut
Jméno:                                                             Místnost:                      Souřadnice:
H
.p   rr     ,-i   r,     ,n   rr     71   rr     ,n   r,     ,n   rr     ri                                  rr     71   r,     ,~i   r,     71
its t    ľ   jj ľ   i                uco    ľ   jj ll   'j ľ   jj ll   jj ll   'j ľ   jj ll   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.
Příklad 4
(a)   Napište, co rozumíme pod problémem syntaktické analýzy pro bezkon-              10+35 bodů textové jazyky.
(b)   Napište deterministický algoritmus pro syntaktickou analýzu (obecných) bezkontextových jazyků. Uveďte, co je vstupem algoritmu a jak se určí jeho výstup. Uveďte složitost algoritmu (není třeba zdůvodňovat).
Oblast strojově snímatelných informací, nezasahujte.
9.1.2007                                        IB102     Automaty a gramatiky                            Cas: 120 minut
Jméno:                                                                   Místnost:                        Souřadnice:
5
.p   rr     ,n   r,     ,n   rr     71   rr     ,n   r,     ,n   rr     ri                                  rr     71   r,     ,~i   r,     71
its t    ľ   jj ^b^j                            uco    ľ   jj ll   'j ľ   jj ll   jj ll   'j ľ   jj ll   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.
Příklad 5
(a)   Definujte, kdy má bezkontextová gramatika vlastnost sebevložení.                10+10+5 bodů
(b)   Napište definici prefixové ekvivalence (~l).
(c)   Jak se nazývá třída jazyků akceptovaných Turingovými stroji?
Uveďte příklad bezkontextová gramatiky, která je necyklická, není vlastní a není        Přiklad  6 jednoznačná. Zdůvodněte, proč není vlastní a proč není jednoznačná.                                  15 bodů
Oblast strojově snímatelných informací, nezasahujte.
Datum:                                      IB102     Automaty a gramatiky                          Cas: 120 minut
Jméno:                                                             Místnost:                      Souřadnice:
rr     71   r,     ,n                                           rr     71   rr     ,n   r,     ,n   rr     71   rr     71   r,     71   rr     71                                  rr     71   r,     71   r,     71
its t    ľ   jj ľ   'j                            uco    ľ   jj ll   'j ľ   jj ll   jj ll   'j ľ   jj ll   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.
Oblast strojově snímatelných informaci, nezasahujte.