Тотален автомат

В основното определение на краен автомат не е необходимо от всички състояния да съществува преход за всички символи. Тотален автомат е автомат, който има дефинирани преходи от всички състояния за всички символи на входната азбука.

Как да построим тотален автомат

Нека имаме този автомат A = ⟨Q, Σ, δ, q₀, F⟩:

Тук не е нарисуван преход от състоянието q₀ за буквата „b“. Ако възникне такава ситуация, казваме, че автоматът не приема дадената входна дума. От гледна точка на формализацията обаче може да не е удобно преходната функция δ да не е определена за някои стойности; тук например не е определена за δ(q₀, b).

Това лесно се решава, като построим еквивалентен автомат, който ще има едно състояние повече — към това състояние ще сочат „липсващите“ преходи, то няма да е крайно и всички по-нататъшни входове ще циклят в него. Този автомат наричаме тотален автомат. Променен еквивалентен автомат би могъл да изглежда така:

Добавихме състоянието q_fail. От останалите състояния прекарахме преход към него тогава и само тогава, когато преди това там нямаше преход. Това състояние не е крайно и циклира за всички по-нататъшни входове. Ако в предишния автомат бяхме попаднали на липсващ преход, тук няма липсващ преход и автоматът би стигнал до състоянието q_fail.

Винаги можем без ограничение на общността да предполагаме, че автоматът има дефинирани преходи за всички комбинации от състояния и знаци от азбуката.

Определение

За тотален автомат A = ⟨Q, Σ, δ, q₀, F⟩ следователно

$$\mathrm{\forall }q\in Q\mathrm{\forall }a\in \mathrm{\Sigma }\mathrm{\exists }r\in Q:\delta (q,a)=r.$$

Източници

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools