Минимизация конечных автоматов
    Пусть – автомат Мили. Расширим действие функций d и l на слова в алфавите X следующим образом:
    , ,
    .
    Функция называется расширенной функцией переходов.
    
    .
    Функция называется расширенной функцией выходов. Согласно приведенному определению она отмечает последний переход в автомате.
    Пусть , i = 1, 2 – автоматы с одинаковыми входными и выходными алфавитами. Состояния автомата А1 и автомата А2 называются неотличимыми (эквивалентными) тогда и только тогда, когда для любого слова справедливо
    .
    Отсюда следует, что при подаче на вход автоматов любого слова выходные слова автоматов, находящихся соответственно в состоянии и совпадают (состояния не различаются по выходу).
    В частности, может быть А1= А2, и речь будет идти о неотличимых состояниях одного автомата. Отношение неотличимости на множестве состояний одного автомата является отношением эквивалентности. Оно разбивает множество всех состояний на непересекающиеся классы. Каждый класс содержит все неотличимые между собой состояния.
    Автоматы А1 и А2 называются неотличимыми (эквивалентными) тогда и только тогда, когда для любого состояния автомата А1 существует эквивалентное ему состояние автомата А2, и для каждого состояния автомата А2 существует эквивалентное ему состояние автомата А1. Неотличимые автоматы осуществляют одно и то же отображение входных слов в выходные.
    Автомат А называется приведенным, если в нем нет эквивалентных состояний. Известно, что для любого автомата существует эквивалентный ему приведенный автомат А. Число состояний в этом автомате является минимальным в классе всех автоматов, эквивалентных автомату . Процедура нахождения приведенного (минимального) автомата для произвольного автомата называется минимизацией конечного автомата .
    Для нахождения минимального автомата множество всех состояний автомата разбивается на классы по отношению неотличимости состояний.
    Пусть – разбиение на , соответствующее отношению неотличимости. Тот факт, что состояния s и t из находятся в одном классе разбиения будем обозначать: .
    Через будем обозначать класс разбиения , содержащий элемент s из .
    Разбиение , соответствующе отношению неотличимости, можно построить согласно следующей процедуре, называемой алгоритмом Мили.
    Строится последовательность разбиений следующим образом:
    Шаг 1.
.
    Иначе одному классу принадлежат те состояния s и t, которые одинаково реагируют на все слова длины 1.
    Шаг к.
    В один класс разбиения объединяются те состояния из класса , которые по любому сигналу х переходят в один и тот же класс разбиения . Поскольку , т. е. получается из измельчением классов, то на шаге к в один класс объединяются те состояния s и t, которые одинаково реагируют на все слова длины к, а поскольку для нетривиальных автоматов число состояний в каждом классе разбиения не более п -1, то для некоторого шага окажется , т. е. число классов перестает увеличиваться. Разбиение и является искомым разбиением , поскольку состояния из одного класса разбиения одинаково реагируют на слова любой длины. Для автомата полагают , в качестве же множества состояний S приведенного автомата берется множество всех классов разбиения p. Функция переходов d приведенного автомата А определяется следующим образом:
   (2.1)
т. е. значением функции переходов d на классе разбиенияp, содержащем некоторый элемент s, является класс разбиения, содержащий элемент, т. е. состояние, в которое переходит состояние s автомата под действием заданного входного значения х. (Такое задание является корректным, поскольку известно, что эквивалентные состояния переходят в эквивалентные по любому входу х).Для функции выходов l полагают:
    ,    (2.2)
т. е. значением функции выходов приведенного автомата на классе разбиения p, содержащем некоторый элемент s, является значение функции выходов исходного автомата в состоянии s при том же входном значении х. Это значение функции одно и то же для всех состояний s из одного класса, так как все состояния в классе эквивалентны.
    Данные о значении функции переходов и выходов заносятся в таблицу, строки которой соответствуют классам разбиения p (состояния автомата А), а столбцы – входным значениям х из Х.
    Поскольку автомат Мура можно рассматривать как частный случай автомата Мили, то описанную процедуру можно использовать и для автомата Мура.