02 Deterministický konečný automat

Last updated Nov 9, 2022

• Patří do regulárních jazyků
• Deterministický konečný automat $M = (Q, \Sigma, \delta, q_{0,}F)$
  • $Q$ - konečná množina vnitřních stavů
  • $\Sigma$ - konečná vstupní abeceda
  • $\delta$ - zobrazení z $Q \times \Sigma$ do $Q$
  • $q_{0}\in Q$ - počáteční stav
  • $F \subseteq Q$ - množina koncových stavů

• Je na ní zapsaný řetězec (sekvence symbolů) - vstup
• Read-only

• Čte jeden symbol a posune se vpravo

• Má nějaký stav, ten je z nějaké množiny stavů, která je konečná
• $q \in Q$
• Chování podle přechodové funkce $\delta$
• Skončí po přečtení celého vstupu, podívá se v jakém stavu skončil
  • pokud v koncovém, přijme vstup - tedy vstup je věta z jazyka generovaného tou gramatikou
  • pokud v jiném, nepřijme vstup

• Dvojice $(q, w)$
  • $q$ - dosud přečtený vstup
  • $w$ - zbytek vstupu, zatím nepřečtený
• Počáteční konfigurace - $(q_{0}, w)$
• Přijímací konfigurace (na konci po přijetí validního vstupu) - $(q, \varepsilon)$

• Značíme $\Large{\vdash}$
  • $\Large{\vdash^+}$ - tranzitivní uzávěr - množina všech konfigurací, do kterých se automat může dostat po libovolném množství přechodů
  • $\Large{\vdash^*}$ - reflexivní uzávěr - to samé, ale i včetně počáteční konfigurace bez žádného přechodu
• Mezi dvěma konfiguracemi, $(q_{1}, aw) \vdash (q_{2}, w)$

• Řetězec $\omega \in \Sigma^$ je přijat konečným deterministickým automatem $M$, jestliže $\exists(q_{0}, \omega) \space \vdash^{}_{M} \space (q,\varepsilon)$ pro nějaké $q\in F$ (existuje posloupnost přechodů z počáteční do přijímací konfigurace)
• $L(M) = {w: w \in \Sigma^{}, \exists q \in F: (q_{0}, w) \vdash^{} (q, \varepsilon) }$ je jazyk přijímaný automatem $M$

$$ \begin{align} \delta(q_{0},0)=q_{2}, \enspace \delta(q_{1},0)=q_{3}, \enspace \delta(q_{2},0)=q_{0}, \enspace \delta(q_{3},0)=q_{1}, \\ \delta(q_{0},1)=q_{1}, \enspace \delta(q_{1},1)=q_{0}, \enspace \delta(q_{2},1)=q_{3}, \enspace \delta(q_{3},1)=q_{2}, \end{align} $$

• Takový problém, který lze vyřešit konečným automatem

• Všechny chybné / neurčené vstupy vedou do jednoho stavu $q_{\emptyset}$
  • Ten není konečný - nelze ty přijmout vstup
  • Má smyčku sám na sebe
• Každý stav reprezentující řetězec, který nepatří do jazyka, musí být v tom automatu