Недетермінований скінченний автомат

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

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

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

Формальне визначення

НДСкА формально представляє п'ятірка, (Q, Σ, Δ, q₀, F), в якій

• скінченна множина станів Q
• скінченна множина вхідних символів Σ
• функція переходу Δ : Q × Σ → P(Q).
• початковий стан q₀ ∈ Q
• набір станів F позначених як допустимі (або кінцеві) стани F ⊆ Q.

Тут, P(Q) позначає множину всіх підмножин Q. Нехай w = a₁a₂ … a_n буде словом в абетці Σ. Автомат M приймає слово w, якщо послідовність станів, r₀,r₁, …, r_n, існує в Q з такими умовами:

1. r₀ = q₀
2. r_i+1 ∈ Δ(r_i, a_i+1), for i = 0, …, n−1
3. r_n ∈ F.

Словами, перша умова каже, що машина стартує зі стану q₀. Друга умова каже, що з кожним символом рядку w, машина переходитиме зі стану до стану відповідно до функції Δ. Остання умова каже, що машина приймає w, якщо останній вхідний символ w спричиняє перехід до одного з допустимих станів. Інакше кажемо, що автомат відкинув рядок. Набір рядків, які приймає автомат — формальна мова, яку розпізнає M, і така мова позначається L(M).

Ми також можемо визначити L(M) в термінах Δ*: Q × Σ* → P(Q) так, що:

1. Δ*(r, ε)= {r} де ε це порожній рядок, і
2. Якщо x ∈ Σ*, a ∈ Σ, і Δ*(r, x)={r₁, r₂,…, r_k}, тоді Δ*(r, xa)= Δ(r₁, a)∪…∪Δ(r_k, a).

Тепер L(M) = {w | Δ*(q₀, w) ∩ F ≠ ∅}.

Зауважте, що наявність лише одного початкового стану не є обов'язковою умовою. Іноді, НДСкА має набір початкових станів. Існує простий метод, що переводить НДСкА з багатьма початковими станами в НДСкА з одним початковим станом.

Застосування НСА

НСА і ДСА тотожні у сенсі, що якщо мова розпізнається НСА, то вона також розпізнається деяким ДСА і навпаки. Встановлення такої тотожності є важливим і корисним. Це корисно, бо часто будування НСА для певної мови значно легше завдання ніж будування ДСА для цієї ж мови. Це важливо, бо НСА можна використати для зменшення складності математичної обчислень необхідних для встановлення багатьох важливих властивостей в теорії алгоритмів. Наприклад, набагато легше довести властивості замкненості регулярної мови із використанням НСА ніж ДСА.

• Об'єднання двох регулярних мов є регулярною мовою.
• Конкатенація двох регулярних мов є регулярною мовою.
• Зірочка Кліні регулярної мови є регулярною мовою.

Див. також

• Теорія автоматів
• Детермінізація НДСкА

Література

Українською

• Гаврилків В. М. Формальні мови та алгоритмічні моделі. — І.-Ф.  : Голіней, 2023. — 180 с.
• Енциклопедія кібернетики, Кратко М. І., т. 1, с. 23.

Іншими мовами

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
• Роджерс Х.. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)