Повний автомат

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

Як побудувати повний автомат

Маємо такий автомат $A=\left<Q, \Sigma, \delta, q_0, F\right>$:

Тут не намальовано перехід зі стану q₀ для літери «b». Якщо виникає така ситуація, кажемо, що автомат не допускає дане вхідне слово. Проте з погляду формалізації може бути незручно, коли функція переходів δ не означена для деяких значень; тут, наприклад, вона не означена для δ(q₀, b).

Це легко розв'язати: побудуємо еквівалентний автомат, який матиме на один стан більше — у цей стан вестимуть «відсутні» переходи, він не буде заключним, а всі подальші входи крутитимуться в ньому по колу. Такий автомат назвемо повним автоматом. Змінений еквівалентний автомат міг би виглядати так:

Ми додали стан $q_{\mbox{fail}}$ (стан-пастку). Із решти станів ми провели в нього перехід тоді й лише тоді, коли раніше там переходу не було. Цей стан не є заключним і для всіх подальших входів переходить сам у себе. Якщо в попередньому автоматі ми натрапляли на відсутній перехід, то тут жодного відсутнього переходу немає, і автомат потрапив би в стан $q_{\mbox{fail}}$.

Тому ми завжди можемо без втрати загальності вважати, що автомат має означені переходи для всіх комбінацій станів і символів алфавіту.

Означення

Отже, для повного автомата $A=\left<Q, \Sigma, \delta, q_0, F\right>$ виконується

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

Джерела

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