Zkouška - 18.06.2012 Barták

Kvíz mi přišel hodně lehký, všechny otázky co tam byly se už tady někde objevily. Celkem jsem se to učil, takže z kvízu 28 bodů z 29. Ale nepřišlo mi, že by tomu přikládal jakýkoli význam.

Ustni:

Mějme A deterministický konečný automat. Zjistěte zda jazyk $L = \{ u | uu^R \in L(A) \}$ je regulární. Nápověda: zkonstruujte dvojcestný automat pro vhodný jazyk a ukažte vztah tohoto jazyka k L. Formulujte a dokažte větu o dvousměrných automatech.

Postup je takový, že si slovo omřížkujeme, abychom poznali začátek a konec (tedy máme slovo #u# kde # není z X). Dvousměrný automat se chová tak, že jde nejprve doprava (pomocí automatu A) na # se otočí, jede doleva (pokračuje automat A). Pokud narazíme na křížek a jsme ve výstupním stavu automatu A, tak slovo je správné. Pustíme se doprava, kde v přijímacím stavu opustíme slovo #u# a dál není výpočet definován. Náčrt automatu je asi takovýto (není to formálně úplně košér, ale uznal to bez problémů)
// q_{00} je poč. stav 2KA, q_0 je poč. stav automatu A, x \in X
\delta(q_{00}, #) -> (q_0, 1)// Začínáme: předáme výpočet automatu A
\delta(p, x) -> (q, 1) // Automat A počítá (p, q jsou nějaké jeho stavy)
\delta(p, #) -> (p_{L}, -1) // Jsme na konci, otáčíme se
\delta(p_{L}, x) -> (q_{L}, -1) // Automat A počítá (p_{L}, q_{L} jsou nějaké jeho stavy)
\delta(q_{F}, #) -> (q_{OK}, 1) // Automat A přijal celé slovo stavem q_{F} a my jsme jeho druhou část přečetli celou
\delta(q_{OK}, x) -> (q_{OK}, 1) // Jdeme doprava, abychom slovo mohli přijmout
\delta(q_{OK}, #) -> (q_{N}, 1) // Slovo přijmeme, q_{OK} je přijímací stav, za koncem slova nesmí být výpočet definován, proto nový stav q_{N}

Otázky a komentáře:
Jak se zbavit mříží # před a za slovem (pomocí levé a pravé derivace podle slova {#} )
Měl jsem špatně to přijímání, jakmile dvoucestný automat slovo přijme a udělá krok doprava, kde není slovo definováno, nesmí tam být ani definován výpočet (já jsem tam recykloval stav q_ {OK}, což znamená, že by tam výpočet ještě mohl běžet a to je zakázáno)
Ještě chtěl napsat Nerodovu větu.

Celkem za 2. Barták mě ještě přemlouval, ať se pokusím o jedničku, ale já jsem byl spokojen (přemlouvá takhle všechny).

Jinak co jsem si všiml, tak z ústní se vás snaží co nejvíc nevyhodit. I když Barták u někoho povzechoval, jak toho je málo a jak to je špatné, pořád tam mu dával další otázky, aby to na tu trojku aspoň bylo.

Já měl zařadit do Chomského hierarchie jazyk (a^n)^2, tzn. sestrojit kontextovou gramatiku (řešení ve studnici) a dokázat, že není bezkontextová pomocí pumping lemmatu pro BKJ (vezmeme n = max(p,q) - z podmínky |vwx|<= q má pumpovací část nejvýš n znaků - když pumpneme jednou nahoru, tak počet znaků vzroste maximálně o n - a počty áček v jednotlivých slovech jsou n^2 < n^2 + n < (n+1)^2, takže nové slovo neleží v jazyce). Dál jsem měl dokázat, že tato gramatika lze obecně převést na odpovídající automat. To mě dost zarazilo, protože převod kontextové gramatiky na lineárně omezený automat jsme nedělali. Na konci mě napadlo, že by možná stačilo dokázat aspoň převod TS na gramatiku typu 0...??? Ale to už jsem nestihnul.
Jinak můžu potvrdit, že když už se dostanete k ústnímu a máte aspoň nějaké netriviální znalosti, tak pan Barták se snaží nechat vás projít.