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

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

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

Еквівалентність НСА та ДСА[ред.ред. код]

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

Позначимо наш НСА як 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, де кожного разу пошук може відбуватись за новими параметрами. Тоді як у, наприклад, лексичних аналізаторах, де одні й ті самі регулярні вирази використовуються постійно, в нагоді стають ДСА.

Посилання[ред.ред. код]

  1. Програма детермінізації НСА (Python)

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