Детермінізація НДСкА

Детермінізація недетермінованого скінченного автомата — полягає в перетворенні недетермінованого скінченного автомату на еквівалентний (тобто такий, що розпізнає таку ж формальну мову) детермінований скінченний автомат.

Еквівалентність НСА та ДСА

Мову яка задана НСА можна задати і ДСА.

Позначимо наш НСА як $N=(Q_{N},\Sigma ,\delta _{N},q_{0},F_{N})$, і будемо шукати ДСА $D=(Q_{D},\Sigma ,\delta _{D},{q_{0}},F_{D})$.

Варто зауважити, що D набагато складніший за N, бо в найгіршому випадку $|Q_{D}|=2^{|Q_{N}|}$. Це викликано тим, що стану D відповідає певна підмножина $Q_{N}$, а їх як відомо $2^{|Q_{N}|}$ (див. булеан).

Правда в більшості випадків станів D набагато менше.

Покажемо еквівалентність конструктивно. Початковий стан D є просто множиною, що складається з одного елемента — початкового стану N. Вхідні алфавіти збігаються.

$F_{D}=\{S\subset Q_{N}|S\cap F_{N}\neq \emptyset \}$

$\forall S\subset Q_{N},\,\forall a\in \Sigma \ \delta _{D}(S,a)=\bigcup _{p\in S}\delta _{N}(p,a)$ (детермінований автомат з стану який позначається множиною, робить перехід в стан який позначається множиною, яка є об'єднанням всіх множин в які переходить недетермінований з кожного свого поточного стану).

Булеанівська конструкція

Булеанівська конструкція (англ. powerset construction, subset construction) — стандартний метод детермінізації НСА який базується на вищеописаному доведенні еквівалентності.

Імітація НСА

Підхід використовний багатьма текстовими редакторами полягає в тому, щоб утворити НСА з регулярного виразу і, тоді імітувати НСА на ходу через використання чогось на кшталт булеанівської конструкції (англ. subset construction).

Алгоритм імітації НСА

Вхід: Вхідний рядок $x$ завершується символом завершення файлу — eof. НСА $N$ з початковим станом $s_{0}$, допустимими станами $F$ і функцією переходів move.

Вихід: Відповідь так, якщо $M$ приймає $x$; інакше ні.

Метод: Алгоритм тримає набір поточних станів $S$, які наразі були досягнуті читанням рядка. Якщо $c$ — наступний вхідний символ, читаємо функцією nextchar(), тоді спочатку обчислюємо move(S, c) і потім замикаємо цю множину за допомогою ε-closure().

1: S = ε-closure(s0);
2: c = nextchar();
3: while ( c != eof ) {
4:   S = ε-closure (move(S, c)) ;
5:   c = nextchar();
6: }
7: if ( S ∩ F != 0 ) return "yes";
8: else return "no";

Швидкодія імітації НСА

За умови обережного втілення, алгоритм може бути дуже швидким. Використана ідея може бути застосована в подібних алгоритмах пошуку на графах. Потрібні структури даних:

1. Два стеки, кожен з яких містить набір станів НСА. Один з цих стеків, старі стани, містить значення $S$ в правій частині 4 рядка. Другий — нові стани. Під час проходу циклу нові стани переносятся в старі.
2. Булевий масив alreadyOn, наповнений станами НСА, щоб позначити, які з них нові. Допоки масив і стек містять одні й ті самі дані, набагато швидше працювати з масивом ніж зі стеком. Провадимо обидві структури лише з огляду на швидкодію.
3. Двомірний масив move[s, a], що містить таблицю переходів НСА. Записи в цій таблиці, які є наборами станів, представлені зв'язними списками.

Для втілення рядка (1), ми маємо встановити кожний запис масиву alreadyOn у FALSE, тоді для кожного стану s в c-closure(so), заштовхнути s у стек oldStates і встановити alreadyOn[s] в TRUE. Ця дія зі станом s, а також реалізація рядку (4), спрощується за допомогою функції яку ми назвемо addState(s). Ця функція заштовхує стан s у newStates, встановлює alreadyOn[s] у TRUE, і викликає себе рекурсивно на всіх станах у move[s, ε] для подальшого обчислення ε-closure(s). Однак, щоб уникнути подвійної роботи, ми маємо бути обачними і ніколи не викликати addState для стану, який уже в стеці newStates.

 9: addState(s) {
10:   push s onto newStates;
11:   alreadyOn[s] = TRUE;
12:   for ( t on move[s, ε] )
13:     if ( !alreadyOn(t) )
14:       addState(t) ;
15: }

Рядок (4) здійснимо через пошук усіх станів s у oldStates. Спочатку знайдемо множину станів move[s, c], де c — це наступний символ на вході, і для кожного з цих станів, який ще не в newStates, ми застосуємо addState до нього.

16: for ( s on oldstates ) {
17:   for ( t on move[s, c] )
18:     if ( !alreadyOn[t] )
19:       addState(t) ;
20:   pop s from oldstates;
21: }

22: for ( s on newstates ) {
23:   pop s from newstates;
24:   push s onto oldstates;
25:   alreadyOn[s] = FALSE;
26: }

Якщо прийняти, що НСА має n станів і m переходів. Вірно втілений 4 рядок має складність O(n+m). Для вхідних даних довжини k загальна робота становить O(k(n+m)).

Обробка вхідних даних довжини k за допомогою ДСА вимагає O(k) часу. Очевидно, що отримати результат за допомогою ДСА набагато швидше ніж за допомогою НСА, але кількість станів у ДСА може бути настільки великою, що виділення пам'яті під таблицю переходів може стати неефективним. Хоча випадки з таким вибухом станів на практиці рідкісні. Імітація НСА може використовуватись такими застосунками як grep, де кожного разу пошук може відбуватись за новими параметрами. Тоді як у, наприклад, лексичних аналізаторах, де одні й ті самі регулярні вирази використовуються постійно, в пригоді стають ДСА.

Література

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation (вид. 2). Addison–Wesley.
• Compilers: Principles, Techniques, and Tools, second edition, Alfred V Aho, Ravi Sethi, and Jeffrey D Ullman, Розділ 3.7.

Див. також

• Мінімізація ДСкА