6. Недетерміновані скінченні автомати без виходу.Алгоритми синтезу нса.

Iнколи трапляються автомати, в яких компонент δ – не функцiя,а деяке вiдношення, тобто в таких автоматах не виконується умова однозначностi переходу. Автомати такого типу називаються недетермiнованими.

Недетермiнований скiнченний автомат (НСА) без виходу (Q,X, δ, , F)визначається так само як i ДСА за винятком того, що в ньому дозволяються переходи в декiлька станiв та e-переходи. Це означає, що для кожного стану q i вхiдної букви a значення δ(q, a) функції переходiв на парi (q, a) є пiдмножиною множини станiв Q, тобто

δ(q, a) = { , , . . . , }. Остання рiвнiсть означає, що проаналiзувавши букву a в станi q автомат може перейти в довiльний зi станів , , . . . , або . В випадку, коли δ(q, a) = ∅ автомат не переходит в жоден стан, "зависає"i вважаємо, що вхiдне слово не розпiзнається

НСА незважаючи на те, що деякi букви слова ще не проаналiзованi автоматом. Це рiвносильно тому, що ДСА перейшов в тупиковий стан. Крiм переходiв в декiлька станiв, в НСА дозволяються також e-переходи (e-такти). При e-переходi головка автомата нiчого не виконує (не читає i не рухається), але стан при цьому може змiнитися на довiльний зi станiв , , . . . , або . Таким чином, функцiя переходiв формально визначається як:

δ : Q × (X ∪ {e}) → ,де через позначається сiм’я всiх пiдмножин множини Q. Прикладом функцiї переходiв НСА є:

Н СА так як i ДСА задаються графами, вершинами яких є стани автомата, а за допомогою стрiлок зображаються переходи, тобто якщо

δ(q, a) = { , , . . . , }, то ми вiдкладаємо k стрiлок з вершини q до кожної з вершин , , . . . , i всi стрiлки помiченi буквою a.

Наприклад, граф розглянутого вище автомата A1 має вигляд (вважаємо, що F = { }):

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

Вважають, що автомат розпiзнає слово ω, якщо принаймi один з обчислювальних шляхiв закiнчується в кінцевому станi.

Щоб визначити строго, коли НСА розпiзнає вхiдне слово ω, потрiбно ввести поняття e-замикання. Назвемо e-замиканням пiдмножини P ⊂ Q множину станiв, якi досягаються з станiв q ∈ P e-переходами (включаючи переходи з q в q). Тобто,

Продовжимо функцiю переходiв δ на множину × (X ∪ {e}),поклавши

а далi продовжимо ї ї на наступним чином:

Тепер можна строго означити, що НСА (Q,X, δ, q₀, F) розпiзнає слово ω, якщо δ({q₀}, ω) ∩ F ∅. Через L(A) позначаємо мову, яка розпiзнається НСА A, тобто

Теоpема. Клас формальних мов, якi розпiзнаються недетермiнованими скiнченними автоматами, замкнений вiдносно конкатинацiї та iтерацiї.

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

Розглянемо НСА A = (Q,X, δ, q₀, F). Для кожного ω∈ позначимо через множину станiв, якi є останнiми станами обчислювальних шляхiв слова ω, тобто = δ({q₀}, ω), де δ – функцiяпереходiв, визначена на множинi × . Зокрема, Q_e = cl_e({q₀}).

Таким чином, слово ω розпiзнається НСА тодii тiльки тодi, коли . Отже, ми можемо взяти цi пiдмножини ⊂Q в якостi

станiв нового еквiвалентного ДСА. Iншими словами, побудуємо ДСА

з наступними компонентами:

, деω∈ , a∈X.

Вiдмiтимо, щокоженстан єпiдмножиноюмножиниQi, отже, єскiнченноюмножиною. Справдi, ⊂ i, отже, | | ≤ .

Далi, якщо = , то = длявсiхa∈X. Звiдсивипливає,щоозначенняфункцiїпереходiв єкоректним. Попереднiй аналiзпоказує, що конструкцiя ДСА є коректною. Дана конструкцiя називається побудовою ДСА за допомогою пiдмножин.

Теоpема 1. Формальна мова розпiзнається НСА тодii лише тодi, коли вона розпiзнається ДСА.

Теорема 1 дає нам простий метод побудови ДСА, який розпiзнає мову L: спершу ми будуємо НСА для L, а потiм перетворюємойого в еквiвалентний ДСА.

Твеpдження. Кожна регулярна мова розпiзнається деякимнедетермiнованим скiнченним автоматом.