# Ústní Barták 20. 5. 2012

<{ForumPost(poster="mathemage", timestamp=2012-05-31 10:56:06)}>
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 :-)
<{/ForumPost}>