Totální automat
Kapitoly: Konečný automat, Totální automat, Nedeterministický konečný automat, Simulace NKA, Převod NKA na DKA
V základní definici konečného automatu není nutné, aby ze všech stavů existoval přechod pro všechny symboly. Totální automat je automat, který má definované přechody ze všech stavů pro všechny symboly vstupní abecedy.
Jak sestrojit totální automat
Mějme tento automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$:
Zde není nakreslený přechod ze stavu q0 pro písmeno „b“. Pokud by taková situace nastala, tak řekneme, že automat nepřijímá dané vstupní slovo. Nicméně z hlediska formalizace nemusí být vhodné, aby přechodová funkce δ nebyla pro některé hodnoty definována; tady např. není definována pro δ(q0, b).
To lze snadno vyřešit tak, že sestrojíme ekvivalentní automat, který bude mít o jeden stav navíc — do tohoto stavu budou mířit „chybějící“ přechody, tento stav nebude koncový a všechny další vstupy už budou cyklit v tomto stavu. Tento automat nazveme totální automat. Upravený ekvivalentní automat by tak mohl vypadat takto:
Přidali jsme stav $q_{\mbox{fail}}$. Z ostatních stavů jsme do něj vedli přechod právě tehdy, pokud tam předtím přechod neexistoval. Tento stav není koncový a cyklí pro všechny další vstupy. Pokud jsme tak v předchozím automatu narazili na chybějící přechod, zde žádný chybějící přechod není a automat by se dostal do stavu $q_{\mbox{fail}}$.
Vždy tak můžeme bez újmy na obecnosti předpokládat, že automat má definované přechody pro všechny kombinace stavů a znaků z abecedy.
Definice
Pro totální automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$ tak platí, že
$$ \forall q \in Q\quad \forall a \in \Sigma\quad \exists r \in Q:\quad \delta(q, a) = r. $$