Теория и реализация языков программирования



Построение детерминированного конечного автомата по недетерминированному


Рассмотрим алгоритм построения по недетерминированному конечному автомату детерминированного конечного автомата, допускающего тот же язык.

Алгоритм 3.2. Построение детерминированного конечного автомата по недетерминированному.

Вход. НКА M = (Q, T, D, q0, F).

Выход. ДКА

M' = (Q', T, D', {q'}_0, F') \; \text{такой что} \; L(M)=L(M')
.

Метод. Каждое состояние результирующего ДКА - это некоторое множество состояний исходного НКА.

В алгоритме будут использоваться следующие функции:

\text{e-closure(R)} \; (R \subseteq Q)
- множество состояний НКА, достижимых из состояний, входящих в R, посредством только переходов по e, то есть множество

S=\bigcup\limits_{q \in R}\{p \mid (q,e) \vdash^* \; (p,e)\}

move(R, a) (R \subseteq Q)
- множество состояний НКА, в которые есть переход на входе a для состояний из R, то есть множество

S=\bigcup\limits_{q \in R}\{p \mid p \in D (q,a)\}

Вначале Q' и D' пусты. Выполнить шаги 1-4:

(1) Определить

{q^'}_0 = e-closure(\{q_0\})
.

(2) Добавить

{q^'}_0
в Q' как непомеченное состояние

(3) Выполнить следующую процедуру:

\begin{align*}& \text{\textbf{while} (в $Q'$ есть непомеченное состояние $R$)\{} \\ & \quad \text{пометить $R$;} \\ & \quad \text{\textbf{for} (каждого входного символа $a \in T$)\{} \\ & \qquad \text{$S = e-closure(move(R; a))$;} \\ & \qquad \text{\textbf{if} ($S \neq \oslash$)\{} \\ & \qquad \quad \text{\textbf{if} ($S \notin Q'$)} \\ & \qquad \qquad \text{добавить $S$ в $Q'$ как непомеченное} \\ & \qquad \qquad \text{состояние;} \\ & \qquad \quad \text{определить $D'(R, a) = S$,} \\ & \qquad \} \\ & \quad \} \\ & \; \} \\ \end{align*}

(4) Определить

F^' = \{S \mid S \in Q', \; S \cap F \neq \oslash \}.

Пример 3.6. Результат применения алгоритма 3.2 приведен на рис. 3.10.


Рис. 3.10. 




Содержание  Назад  Вперед