Automat całkowity
Kapitoly: Automat skończony, Automat całkowity, Niedeterministyczny automat skończony, Symulacja NKA, Konwersja NKA na DKA
W podstawowej definicji automatu skończonego nie jest konieczne, aby istniało przejście ze wszystkich stanów do wszystkich symboli. Automat całkowity to automat, który ma zdefiniowane przejścia ze wszystkich stanów dla wszystkich symboli alfabetu wejściowego.
Jak skonstruować automat całkowity
Rozważmy automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$:
Tutaj przejście ze stanu q0 dla litery "b" nie jest narysowane. Gdyby taka sytuacja miała miejsce, powiedzielibyśmy, że automat nie akceptuje słowa wejściowego. Jednak z punktu widzenia formalizacji może nie być właściwe, aby funkcja przejścia δ nie była zdefiniowana dla niektórych wartości; tutaj, na przykład, nie jest ona zdefiniowana dla δ(q0, b).
Można to łatwo rozwiązać, konstruując równoważny automat, który ma jeden dodatkowy stan - "brakujące" przejścia będą kierowane do tego stanu, stan ten nie będzie terminalny, a wszystkie inne wejścia będą już cyklicznie w tym stanie. Taki automat nazwiemy automatem całkowitym. Zmodyfikowany równoważny automat może wyglądać następująco:
Dodaliśmy stan $q_{\mbox{fail}}$. Doprowadziliśmy do niego przejście z innych stanów na wypadek, gdyby przejście nie istniało tam wcześniej. Ten stan jest niekońcowy i cyklicznie przechodzi przez wszystkie inne wejścia. Tak więc, gdybyśmy napotkali brakujące przejście w poprzednim automacie, tutaj nie ma brakującego przejścia i automat przejdzie do stanu $q_{\mbox{fail}}$.
W ten sposób możemy zawsze zakładać bez utraty ogólności, że automat ma zdefiniowane przejścia dla wszystkich kombinacji stanów i znaków alfabetu.
Definicja
Zatem dla całego automatu $A=\left<Q, \Sigma, \delta, q_0, F\right>$ zachodzi następująca zależność
$$ \forall q \in Q\quad \forall a \in \Sigma\quad \exists r \in Q:\quad \delta(q, a) = r. $$