Минимизация конечного автомата

Конечный автомат может содержать лишние состояния двух типов: недостижимые и эквивалентные состояния.

Определение Два различных состояния и в конечном автомате называются n -эквивалентными, n Î N È{0}, если, находясь в одном их этих состояний и получив на вход любую цепочку символов w: w Î T^*, |w| £ n, автомат может перейти в одно и то же множество конечных состояний.

Определение Состояние q КА называется недостижимым, если к нему нет пути из начального состояния автомата.

Определение КА, не содержащий недостижимых и эквивалентных состояний, называется приведенным или минимальным КА.

В теории КА доказано, что каждое регулярное множество распознается единственным для данного множества ДКА с минимальным числом состояний. Рассмотрим алгоритмы построения минимального ДКА.