Ústní Barták 20. 5. 2012

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Ústní Barták 20. 5. 2012

Příspěvek od mathemage »

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 :-)
Carpe Diem!
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“