2. Доказательство минимальности автомата
Докажем, что 
A(
(
)
=
(
)).
Проведем доказательство этого свойства индукцией по длине слова . При этом дополнительно будет доказываться вспомогательное утверждение: если (a,qi)=qr, то (a,q(i))Qr, а состояния (a,q(i)) и q(r) являются неотличимыми.
Базис индукции
a A( (a) = (a, qi)= (a,q(i)) = (a)).
При этом (a,q(i)) и q(r) неотличимые состояния автомата , где qr = (a, qi).
Индуктивное предположение
A( k ( ) = ( )).
При этом ( ,q(i)) и q(r) неотличимые состояния автомата , где qr = ( , qi).
Индуктивный переход
Пусть
=
a
произвольное слово длины m
= k
+
1.
Тогда справедливы соотношения:
( ) = ( ) (a, ( , qi)
( ) = ( ) (a, ( ,q(i))).
По индуктивному предположению ( )= ( ).
Покажем, что (a, ( , qi) = (a, ( ,q(i))).
Пусть ( , q(i)) = qj. Тогда из вспомогательного индуктивного предположения следует, что состояния qj и q(r), где qr = ( , qi) неотличимые.
Поэтому справедливы равенства, доказывающие справедливость индуктивного перехода для основного свойства:
(a, ( , qi) = (a, qr) = (a, q(r)) = (a, qj)= = (a, ( ,q(i))).
Покажем справедливость индуктивного перехода для вспомогательного утверждения.
Рассмотрим состояния ( a, q(i)) и q(h), где qh = ( a, qi). Покажем, что эти состояния неотличимые.
Так как qj и q(r) Qr, то состояния ( a, q(i)) и (a, q(r)) являются неотличимыми.
Так как qh = ( a, qi)= (a, qr), то h = ((a, q(r))).
Следовательно, h = ((a, qj)).
Значит, (a, qj), (a, q(j)) Qh.
Поэтому состояния ( a, q(i)) и q(h), где qh = ( a, qi), являются неотличимыми.
Свойство доказано.
Покажем, что все состояния автомата являются отличимыми.
Пусть qi,
qj
Q.
Тогда состояния q(i)
и q(j)
отличимые. Поскольку
=
и
=
,
то
.
Следовательно, состояния qi
и
qj
также являются отличимыми.
Поскольку i(
=
)
и i(
=
),
то множества функций, вычисляемых
автоматами
и ,
совпадают.
Окончательно получаем, что автоматы и эквивалентные, причем автомат минимальный.
Доказательство окончено.
Замечание. Использованное в доказательстве теоремы преобразование автомата в эквивалентный ему минимальный автомат фактически состоит в том, чтобы заменить всякий класс неотличимых состояний автомата на одно состояние.
Если автоматы представляются диаграммами перехода, то автомат можно получить, если одновременно заменить все состояния каждого класса неотличимых состояний в одно состояние. Всякая дуга, выходящая из вершины, обозначающей произвольное состояние , заменяется на дугу с сохранением разметки, образованной входным и выходным символами.
Такая дуга для автомата соединяет состояния, соответствующие классам неотличимых состояний начала и конца исходной дуги для .
Для автомата, приведенного на рис. 7.6 и имеющего неотличимые состояния q0 и q1, такое преобразование имеет вид, изображенный на рис.7.9.
0(0)
0(0)
0(0)
q1 q0 q0
1(1) 1(1) 1(1) 1(0)
1(0)
A q2 B q1
1(1) 1(1)
Рис. 7.9