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

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

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

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

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

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

• скінченна множина станів Q
• скінченна множина вхідних символів Σ
• функція переходу Δ : Q × Σ → P(Q).^[1]
• початковий стан 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 ≠ ∅}.

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

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

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

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

Див. також

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