Алгоритм удаления недостижимых состояний.

Алгоритм построения ДКА по НКА.

Вход: M = (K, V, F, H, S) - недетерминированный конечный автомат.

Выход: M’ = (K’, V, F’, H’, S’) - детерминированный конечный автомат, допускающий тот же язык, что и автомат М.

Метод:

1. Множество состояний К’ автомата М’ состоит из всех подмножеств множества К автомата М. Каждое состояние из К’ будем обозначать [A₁A₂...A_n], где A_i Î K.

2. Функция переходов F’ автомата М’ строится следующим образом: F’ ([A₁A₂...A_n], t) = [B₁B₂...B_m], где для любого 1 £ i £ n существует 1 £ j £ m так, что F(A_i, t) = B_j .

3. Пусть H = {H₁, H₂, ..., H_k}, тогда H’ = [H₁, H₂, ..., H_k].

4. Пусть S = {S₁, S₂, ..., S_p}, тогда S’ - все состояния из K’, имеющие вид [...S_i...], S_i Î S для какого-либо 1 £ i £ p.

После построения из нового ДКА необходимо удалить все недостижимые состояния.

Состояние kÎK в конечном автомате M = (K, V, F, H, S) называется недостижимым, если ни при какой входной цепочке wÎV⁺ невозможен переход автомата из начального состояния Н в состояние k. Иначе состояние называется достижимым.

Пусть R – множество достижимых состояний; Р_i – множество текущих активных состояний автомата M = (K, V, F, H, S) на i-м шаге алгоритма. Результатом работы алгоритма является полное множество достижимых состояний R.

1.

2.

3.

4. Если , то выполнение алгоритма закончено, иначе

. Перейти к шагу 3.

Рассмотрим пример, иллюстрирующий работу алгоритма преобразования недетерминированного КА в ДКА.

Пример 3.4

Пусть дан конечный автомат M = ({H, A, B, S}, {0, 1}, F, {H}, {S}), где F: F(H, 1) = B, F(B, 0) = A, F(A, 1) = B, F(A, 1) = S .

Граф переходов данного автомата выглядит следующим образом (рис. 3.10):

Рис. 3.10. Граф переходов недетерминированного КА

Очевидно, что заданный конечный автомат является недетерминированным, так как из состояния А по символу ‘1’ возможен переход как в состояние В, так и в состояние S. Преобразуем заданный НКА в детерминированный КА.

Множество состояний эквивалентного ДКА будет следующим:

K’ = {[H], [A], [B], [S], [HA], [HB], [HS], [AB], [AS], [BS], [HAB], [HAS], [ABS], [HBS], [HABS]}

Построим функцию переходов эквивалентного ДКА:

F’([A], 1) = [BS] F’([H], 1) = [B]

F’([B], 0) = [A] F’([HA], 1) = [BS]

F’([HB], 1) = [B] F’([HB], 0) = [A]

F’([HS], 1) = [B] F’([AB], 1) = [BS]

F’([AB], 0) = [A] F’([AS], 1) = [BS]

F’([BS], 0) = [A] F’([HAB], 0) = [A]

F’([HAB], 1) = [BS] F’([HAS], 1) = [BS]

F’([ABS], 1) = [BS] F’([ABS], 0) = [A]

F’([HBS], 1) = [B] F’([HBS], 0) = [A]

F’([HABS], 1) = [BS] F’([HABS], 0) = [A]

Начальное состояние эквивалентного ДКА:

S’ = {[S], [HS], [AS], [BS], [HAS], [ABS], [HBS], [HABS]}

Применим алгоритм удаления недостижимых состояний.

Множество достижимых состояний ДКА: R={[H], [B], [A] и [BS]}, поэтому все остальные состояния удаляются.

Таким образом, M’ = ({[H], [B], [A], [BS]}, {0, 1}, F’, H, {[BS]}), где

F’([A], 1) = [BS] F’([H], 1) = [B]

F’([B], 0) = [A] F’([BS], 0) = [A]

Обозначим состояние BS как S, тогда

M’ = ({[H], [B], [A], [S]}, {0, 1}, F’, H, {[S]}), где

F’([A], 1) = [S] F’([H], 1) = [B]

F’([B], 0) = [A] F’([S], 0) = [A]

Граф переходов полученного ДКА изображен на рис. 3.11.

Рис. 3.11. Граф переходов детерминированного КА

Этот автомат легко преобразовать к полностью определенному виду (рис. 3.12):

Рис. 3.12. Граф переходов полностью определенного детерминированного КА

В процессе построения распознавателей при решении вопроса о необходимости преобразования НКА в ДКА следует руководствоваться принципом разумной достаточности, так как при выполнении преобразований число состояний автомата может значительно возрасти, что, в свою очередь, влечет за собой увеличение затрат на моделирование. Поэтому не всегда выполнение преобразования автомата к детерминированному виду является обязательным.