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



Построение детерминированного конечного автомата с минимальным числом состояний


Рассмотрим теперь алгоритм построения ДКА с минимальным числом состояний, эквивалентного данному ДКА [?].

Пусть M = (Q, T, D, q0, F) - ДКА. Будем называть M всюду определенным, если D(q, a)

, для всех
q \in Q
и
a \in T
.

Лемма. Пусть M = (Q, T, D, q0, F) - ДКА, не являющийся всюду определенным. Существует всюду определенный ДКА M', такой что L(M) = L(M').

Доказательство. Рассмотрим автомат

M^'=(Q\cup\{q^'\},T,D^',q_0,F),

где q'

Q - некоторое новое состояние, а функция D' определяется следующим образом:

(1) Для всех

q \in Q
и
a \in T
, таких что D(q, a)
,, определить D'(q, a) = D(q, a).

(2) Для всех

q \in Q
и
a \in T
, таких что D(q, a) =
, определить D'(q, a) = q'.

(3) Для всех

a \in T
определить D'(q', a) = q'.

Легко показать, что автомат M' допускает тот же язык, что и M.

Приведенный ниже алгоритм получает на входе всюду определенный автомат. Если автомат не является всюду определенным, его можно сделать таковым на основании только что приведенной леммы.

Алгоритм 3.4. Построение ДКА с минимальным числом состояний.

Вход. Всюду определенный ДКА M = (Q, T, D, q0, F).

Выход. ДКА

M' = (Q', T, D', q'_0, F')
, такой что L(M) = L(M') и M' содержит наименьшее возможное число состояний.

Метод. Выполнить шаги 1-5:

(1) Построить начальное разбиение ? множества состояний из двух групп: заключительные состояния Q и остальные Q - F, то есть ? = {F, Q - F}.

(2) Применить к ? следующую процедуру и получить новое разбиение ?new:

for (каждой группы G в ?){ разбить G на подгруппы так, чтобы состояния s и t из G оказались в одной подгруппе тогда и только тогда, когда для каждого входного символа a состояния s и t имеют переходы по a в состояния из одной и той же группы в ?, заменить G в ?new на множество всех полученных подгрупп, }

(3) Если ?new = ?, полагаем ?res = ? и переходим к шагу 4, иначе повторяем шаг 2 с ? := ?new.

(4)

\begin{align*} & \text{Пусть $\prod\nolimits_{res} = \{G_1, \ldots , G_n\}$. Определим:} \\ & \text{$Q'=\{G_1,\ldots, G_n\}$;} \\ & \text{$q'_0=G$, где группа $G \in Q'$ такова, что $q_0 \in G$;} \\ & \text{$F=\{ G \mid\ G \in Q'$ и $G \cap F \neq \oslash$\};}\\ & \text{$D'(p',a)=q'$, если $D(p,a)=q$, где $p \in p'$ и $q \in q'$} \end{align*}

Таким образом, каждая группа в ?res становится состоянием нового автомата M'. Если группа содержит начальное состояние автомата M, то эта группа становится начальным состоянием автомата M'. Если группа содержит заключительное состояние M, она становится заключительным состоянием M'. Отметим, что каждая группа ?res либо состоит только из состояний из F, либо не имеет состояний из F. Переходы определяются очевидным образом.

(5) Если M' имеет "мертвое"состояние, то есть состояние, которое не является допускающим и из которого нет путей в допускающие, удалить его и связанные с ним переходы из M'. Удалить из M' также все состояния, недостижимые из начального.

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


Рис. 3.15. 




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