Ústní Barták 20. 5. 2012

Formální definice (nedeterministického) zásobníkového automatu
přijímání koncovými stavy a přijímaní prázdným zásobníkem
tvrzení o vztahu jazyků přijímané těmito 2 způsoby (jsou si oba rovné, chtělo to ukázat převod oběma směry)
sestrojit ZA přijímající koncovými stavy jazyk $\{ucv| u, v \in \{a, b\}^*, |u| e |v|\}$ (tady jsem se musel dodatečně zeptat, ale je to nad abecedou $\{a, b, c\}$) a převést na ZA přijímající prázdným zásobníkem (pokud bylo jasně popsáno v předchozím důkazu, stačilo se na něj jen odvolat a nemuselo se explicitně popisovat).

Automat vypadal takto (popsáno 7ici $(Q, X, Y, \delta, q_0, Z_0, F)$ klasicky jako na slidech):
$$M := (\{q_0, q_{OK}, q_{bad}\}, \{a, b, c\}, \{Z_0, D\}, \delta, q_0, Z_0, \{q_{OK}\})$$
přechodová fce (pro zjednodušení zápisu buď $x \in {a, b}$)$$\delta(q_0, x, Z_0) = \{(q_0, DZ_0)\}$$$$\delta(q_0, x, D) = \{(q_0, DD)\}$$...délka "u"$$\delta(q_0, c, D) = \{(q_{OK}, \lambda)\}$$...umažu první D, abych se dostal při stejně dlouhých u, v zpátky na podložku$$\delta(q_{OK}, x, D) = \{(q_{OK}, \lambda)\}$$...ubírám další D podle délky v$$\delta(q_{OK}, x, Z_0) = \{(q_{bad}, Z_0)\}$$...délky u, v se vyrovnaly -> špatné$$\delta(q_{bad}, x, Z_0) = \{(q_{OK}, Z_0)\}$$...délky v už je zase ostře větší$$\delta(q_0, c, Z_0) = \{(q_{bad}, Z_0)\}$$... případ$u = \lambda$, pokud nepřijde po "c" aspoň 1 znak a nebo b, nemůžu slovo přijmout

Snad jsem to vystihl všechno a dobře, pokud jsem nezachytil nějaký okrajový případ, neváhejte zkritizovat :-)