yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->5.3 Недостижимые состояния

Дискретная математика

5.3 Недостижимые состояния

 

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

Шаг 1: записать одноэлементное множество, в которое входит  начальное состояние;

Шаг 2: дополнить это множество состояниями, в которые переходит автомат из состояний, уже присутствующих  в  множестве  при  воздействии любых входных символов;

Шаг 3: если на шаге 2 множество не пополняется новыми элементами, то получен  исчерпывющий  список  достижимых  состояний;  остальные состояния КА недостижимы.

Конечный автомат, из которого исключены недостижимые и  эквивалентные состояния называется минимальным КА.

 

 

29