✖

Automat zupełny

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 = ⟨Q, Σ, δ, q0, F⟩:

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 qfail (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 qfail.

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 = ⟨Q, Σ, δ, q0, F⟩ zachodzi więc

∀q∈Q∀a∈Σ∃r∈Q:δ(q,a)=r.

Źródła

Rozdziały: Automat skończony, Automat zupełny, Niedeterministyczny automat skończony, Symulacja NFA, Przekształcenie NFA w DFA