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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Формальне визначення[ред.ред. код]

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

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

Тут, P(Q) позначає множину всіх підмножин Q. Нехай w = a1a2 ... an буде словом в абетці Σ. Автомат M приймає слово w якщо послідовність станів, r0,r1, ..., rn, існує в Q з такими умовами:

  1. r0 = q0
  2. ri+1 ∈ Δ(ri, ai+1), for i = 0, ..., n−1
  3. rnF.

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

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

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

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

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

Застосування НСА[ред.ред. код]

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

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

Див. також[ред.ред. код]

Джерела[ред.ред. код]

Примітки[ред.ред. код]

  1. У випадку ДСА маємо таку функцію переходу δ : Q × Σ → Q.