Automat zupełny
Kapitoly: Automat skończony, Automat zupełny, Niedeterministyczny automat skończony, Symulacja NFA, Przekształcenie NFA w DFA
W podstawowej definicji automatu skończonego nie jest konieczne, żeby z każdego stanu istniało przejście dla każdego symbolu. Automat zupełny (nazywany też totalnym) to automat, który ma określone przejścia z każdego stanu dla każdego symbolu alfabetu wejściowego.
Jak zbudować automat zupełny
Weźmy taki automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$:
Nie ma tu na przykład narysowanego przejścia ze stanu q0 dla litery „b”. Gdyby taka sytuacja nastąpiła, powiemy, że automat nie akceptuje danego słowa wejściowego. Z punktu widzenia formalizacji może jednak nie być wygodne, żeby funkcja przejścia δ dla niektórych wartości nie była określona; tutaj nie jest określona np. dla δ(q0, b).
Łatwo to rozwiązać: zbudujemy równoważny automat, który będzie miał jeden stan więcej – do tego stanu będą prowadzić „brakujące” przejścia, stan ten nie będzie akceptujący, a wszystkie kolejne wejścia będą już krążyć w pętli w tym stanie. Taki automat nazwiemy automatem zupełnym. Poprawiony równoważny automat mógłby więc wyglądać tak:
Dodaliśmy stan $q_{\mbox{fail}}$ (ang. fail – porażka), nazywany często stanem pułapką. Z pozostałych stanów poprowadziliśmy do niego przejście dokładnie wtedy, gdy wcześniej takiego przejścia nie było. Ten stan nie jest akceptujący i ma pętlę dla wszystkich kolejnych wejść. Tam, gdzie w poprzednim automacie trafilibyśmy na brakujące przejście, tutaj żadnego brakującego przejścia nie ma i automat trafiłby do stanu $q_{\mbox{fail}}$.
Zawsze więc możemy bez straty ogólności zakładać, że automat ma określone przejścia dla wszystkich kombinacji stanów i znaków alfabetu.
Definicja
Dla automatu zupełnego $A=\left<Q, \Sigma, \delta, q_0, F\right>$ zachodzi więc
$$ \forall q \in Q\quad \forall a \in \Sigma\quad \exists r \in Q:\quad \delta(q, a) = r. $$