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

Среди состояний автомата могут быть такие, которые не достижимы из начального состояния ни для какой входной цепочки, например, таковым состояниям является S4, т.к. в таблице нет перехода в S4.

	0	1
S0 S1 S2 S3 S4 S5 S6 S7 S8	S1 S2 S2 S5 S5 S3 S8 S0 S3	S5 S7 S5 S7 S6 S1 S0 S1 S6	0 1 1 0 0 0 1 1 0

Такие состояния называют недостижимыми и соответствующие им строки можно удалить.

	0	1
S0 S1 S2 S3 S5 S6 S7 S8	S1 S2 S2 S5 S3 S8 S0 S3	S5 S7 S5 S7 S1 S0 S1 S6

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

Для любого данного автомата – составить список достижимых состояний.

1. Начать список в начальном состоянии.

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

Если эта процедура перестаёт давать новые состояния, то все достижимые состояния получены, а все остальные можно удалить из автомата. Число шагов процедуры ограничено числом состояний данного автомата.

S0-> S1 и S5; S1 -> S2 и S7; S5-> S3 и S1. Переходов в другие состояния нет => S4, S6 и S8 - недостижимы, и автомат можно сократить.

	0	1
S0 S1 S2 S3 S4 S5 S7	S1 S2 S2 S5 S5 S3 S0	S5 S7 S5 S7 S6 S1 S1

Приведённые автоматы.

Определение: Автомат приведённый, если он не содержит недостижим состояний и никакие 2 его состояний не эквивалентны друг другу.

Замечание: Если автомат не приведённый, то можно получить эквивалентный ему автомат с меньшим числом состояний, как раннее было показано.

Осуществляя приведение различными способами или начиная с разных эквивалентных автоматов, можно предположить, что полученные приведённые автоматы окажутся разными. Однако, они фактически одинаковы во всех отношениях, за исключением имён, которыми названы их состояния.

Значит, какой бы распознаватель ни был выбран для некоторой проблемы распознавания и каким бы образом ни происходило бы приведение его состояний, можно построить только 1 приведённый автомат. Этот автомат называется минимальным автоматом.