od mathemage » 31. 5. 2012 10:56
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
(tady jsem se musel dodatečně zeptat, ale je to nad abecedou
) 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
)
klasicky jako na slidech):
)
přechodová fce (pro zjednodušení zápisu buď
)
 = \{(q_0, DZ_0)\})
 = \{(q_0, DD)\})
...délka "u"
 = \{(q_{OK}, \lambda)\})
...umažu první D, abych se dostal při stejně dlouhých u, v zpátky na podložku
 = \{(q_{OK}, \lambda)\})
...ubírám další D podle délky v
 = \{(q_{bad}, Z_0)\})
...délky u, v se vyrovnaly -> špatné
 = \{(q_{OK}, Z_0)\})
...délky v už je zase ostře větší
 = \{(q_{bad}, Z_0)\})
... případ
, 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
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 [latex]\{ucv| u, v \in \{a, b\}^*, |u|
e |v|\}[/latex] (tady jsem se musel dodatečně zeptat, ale je to nad abecedou [latex]\{a, b, c\}[/latex]) 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 [latex](Q, X, Y, \delta, q_0, Z_0, F)[/latex] klasicky jako na slidech):
[latex]M := (\{q_0, q_{OK}, q_{bad}\}, \{a, b, c\}, \{Z_0, D\}, \delta, q_0, Z_0, \{q_{OK}\})[/latex]
přechodová fce (pro zjednodušení zápisu buď [latex]x \in \{a, b\}[/latex])
[latex]\delta(q_0, x, Z_0) = \{(q_0, DZ_0)\}[/latex]
[latex]\delta(q_0, x, D) = \{(q_0, DD)\}[/latex]
...délka "u"
[latex]\delta(q_0, c, D) = \{(q_{OK}, \lambda)\}[/latex]
...umažu první D, abych se dostal při stejně dlouhých u, v zpátky na podložku
[latex]\delta(q_{OK}, x, D) = \{(q_{OK}, \lambda)\}[/latex]
...ubírám další D podle délky v
[latex]\delta(q_{OK}, x, Z_0) = \{(q_{bad}, Z_0)\}[/latex]
...délky u, v se vyrovnaly -> špatné
[latex]\delta(q_{bad}, x, Z_0) = \{(q_{OK}, Z_0)\}[/latex]
...délky v už je zase ostře větší
[latex]\delta(q_0, c, Z_0) = \{(q_{bad}, Z_0)\}[/latex]
... případ [latex]u = \lambda[/latex], 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 :-)