✖

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

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

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

Маємо такий автомат A = ⟨Q, Σ, δ, q0, F⟩:

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

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

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

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

Означення

Отже, для повного автомата A = ⟨Q, Σ, δ, q0, F⟩ виконується

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

Джерела

Розділи: Скінченний автомат, Повний автомат, Недетермінований скінченний автомат, Симуляція недетермінованого автомата, Перетворення НСА на ДСА