Формулировка: Для любого конечного автомата существует неотличимый от него минимальный автомат единственный с точностью до изоморфизма, имеющий состояний, если множество состояний автомата разбивается на классов эквивалентности . 
Доказательство: А) постановка задачи
Среди автоматов эквивалентных (неотличимых от ) найти автомат с наименьшим числом состояний. По определению неотличимости: если исходный автомат , где .
В) Пусть и принадлежат одному классу эквивалентности , тогда для из входного алфавита , следующие состояния должны принадлежать одному и тому же классу эквивалентности (возможно другому) , . Докажем это: , . Предположим, что и — отличимы. Это означает, что найдется строка , такая что . Но мы знаем, что можно представить, как , это означает, что т.е. мы показали, что состояния и различны.
С) Минимальный автомат определим так: , где (множество классов эквивалентности) будут равны тому же состоянию , где вычисляется так: , где .
Физический смысл: — это функция, заданная на двух множествах: на множестве входных знаков и множестве состояний, которое мы ввели. Результат функции новое состояние.
— определим аналогично: таким образом, мы строим отображение (функцию) выхода минимального автомата.
D) Построенный автомат неотличим от автомата , причем автомат не имеет неотличимых состояний.
Е) Докажем, что минимален. Т.е. не имеет неотличимых состояний:
a) Предположим, что не минимален, т.е. существует с меньшим числом состояний .
b) По определению неотличимости состояний, для каждого состояния найдется неотличимое состояние , но так как имеет меньшее число состояний, то какие, то два состояния неотличимы от одного состояния .
c) В силу транзитивности неотличимости т.е. если и неотличимы от какого-то состояния , то и неотличимы между собой ( ) откуда следует, что в автомате имеются неотличимые состояния, что противоречит нашему допущению (пункт а).
F) Докажем, что любой минимальный автомат автомата изоморфен автомату
a) Пусть любой другой минимальный автомат от автомата т.е. в соответствии с пунктом Е, и имеют одинаковое число состояний, причем и неотличимы.
b) Тогда различные состояния неотличимы от различных состояний , поэтому между и можно установить изоморфизм.
Замечание 1. Для того чтобы воспользоваться теоремой, для построения минимального автомата необходимо уметь находить классы эквивалентности состояний.
Замечание 2. Определение неотличимости не содержит конструктивной процедуры проверки неотличимости двух состояний, так как предполагает перебор по бесконечному множеству входных строк.