Пример 2. Применим процедуру из теоремы о детерминизации к НКА N1 из примера 1 (рис

Применим процедуру из теоремы о детерминизации к НКА N₁ из примера 1 (рис. 5.16).

Рис. 5.16. Диаграмма НКА

Заметим, что состояние 4 исчезло, так как в автомате N₁ в него можно было попасть только по ε -переходу.

На втором этапе детерминизируем M₁. ДКА A будет иметь 16 состояний:

Q^A= {∅, {0}, {1}, {2}, {3}, {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}, {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}, {0, 1, 2, 3}}.

Во множество заключительных состояний войдут состояния, содержащие заключительное состояние 3 автомата M₁:

F^A= {{3}, {0, 3}, {1, 3}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}, {0, 1, 2, 3}}.

Функция переходов ΦA определена в следующей таблице

На самом деле нас интересуют лишь те состояния, в которые можно попасть из начального состояния {0}. Несложный анализ показывает, что их только три: {0, 1}, {0, 2} и {0, 1, 3}. Остальные состояния не достижимы из {0} и, следовательно, не влияют на работу автомата A. Их можно отбросить. Таким образом, в диаграмме автомата остаются 4 состояния, показанные на рис. 5.17.

Замечание. В рассмотренном примере у построенного ДКА A оказалось не больше состояний, чем у исходного НКА N₁. К сожалению, это не всегда так. Существуют примеры НКА с n состояниями, для которых эквивалентные ДКА содержат не менее 2ⁿ состояний.

Рис. 5.17. Диаграмма ДКА

Дата добавления: 2014-01-05