Материал: Ковригин Теория автоматов Лабораторный практикум 2012

Таблица 6.1 Таблица переходов недетерминированного конечного автомата,

соответствующего регулярному выражению 101((0|1)(0|1)(0|1))+101

Синтез детерминированного конечного автомата

Рассмотрим синтез детерминированного конечного автомата по алгоритму 6.3.

1.Строим множество zε(S0) = {S0}, ставим ему в соответствие состояние ДКА A, которое будет стартовым (табл. 6.2).

2.Строим множество zε(M0(A)) = Ø, т.е. из A по 0 будет переход

97

в тупиковое состояние. Строим множество zε(M1(A)) = {S2}, ставим ему в соответствие состояние ДКА B. Заполняем соответствующим образом таблицу переходов. Помечаем проанализированное состояние (табл. 6.3).

Таблица 6.2

Синтез таблицы переходов ДКА (шаг 1)

3. Строим множество zε(M0(B)) = {S2}, ставим ему в соответствие состояние ДКА C. Строим множество zε(M1(B)) = Ø, т.е. из B по 0 будет переход в тупиковое состояние. Заполняем соответствующим образом таблицу переходов. Помечаем проанализированное состояние (табл. 6.4).

4.Строим множество zε(M0(C)) = Ø, т.е. из C по 0 будет переход

втупиковое состояние. Строим множество zε(M1(C)) = {S3, S4, S5, S7}, ставим ему в соответствие состояние ДКА D. Заполняем соответствующим образом таблицу переходов. Помечаем проанализированное состояние (табл. 6.5).

5.Строим множество zε(M0(D)) = {S6, S9, S10, S12}, ставим ему

всоответствие состояние ДКА E. Строим множество zε(M1(D)) =

98

= {S7, S9, S10, S12}, ставим ему в соответствие состояние ДКА F. Заполняем соответствующим образом таблицу переходов. Помечаем проанализированное состояние (табл. 6.6).

Таблица 6.5

Синтез таблицы переходов ДКА (шаг 4)

FS8, S9, S10, S12

6.Строим множество zε(M0(E)) = {S11, S14, S15, S17}, ставим ему в соответствие состояние ДКА G. Строим множество

zε(M1(E)) = {S13, S14, S15, S17}, ставим ему в соответствие состояние ДКА H. Заполняем соответствующим образом таблицу переходов. Помечаем проанализированное состояние (табл. 6.7).

7.Строим множество zε(M0(F)) = {S11, S14, S15, S17}. Состоя-

ние, соответствующее такому множеству, уже есть в ДКА (G).

Строим множество zε(M1(F)) = {S13, S14, S15, S17}. Состояние, соответствующее такому множеству, также есть в ДКА (H). Заполняем соответствующим образом таблицу переходов. Помечаем проанализированное состояние (табл. 6.8).

8.Строим множество zε(M0(G)) = {S4, S5, S7, S16, S19, S20},

ставим ему в соответствие состояние ДКА I. Строим множество

zε(M1(G)) = {S4, S5, S7, S18, S19, S20}, ставим ему в соответствие состояние ДКА J. Заполняем соответствующим образом таблицу переходов. Помечаем проанализированное состояние (табл. 6.9).

99