Автомат недетермінований

Матеріал з Вікіпедії — вільної енциклопедії.

Автома́т недетерміно́ваний — автомат, який при даному вхідному символі і внутрішньому стані може переходити в декілька різних внутрішніх станів.

Формально, недетермінований автомат — це п'ятірка <X, Y, Q, Φ, Ψ>, така, що відображення Ψ: X × Q → Q не є однозначним.

За аналогією з теорією детермінованих автоматів можна ввести поняття представлення (породження) множин для недетермінованих автоматів. Якщо два скінченних автомати, які представляють одну й ту саму множину вважати еквівалентними, то існує алгоритм, який дозволяє по кожному скінченному недетермінованому автомати побудувати еквівалентний йому скінченний детермінований автомат. При цьому, зрозуміло що, детермінований автомат має більшу кількість станів, ніж недетермінований автомат. В загальному випадку, для довільних автоматів це твердження невірне. Наприклад, клас множин, які породжуються недетермінованими автоматами зі стековою пам'яттю ширше, ніж клас множин, які породжуються такими ж детермінованими автоматами.