Определение: Комбинационный автомат- это конечный автомат, у которого выходной знак зависит от входного, и не зависит от состояния автомата. 
Формализуем определение: если задан автомат , то для всех знаков и любой пары , должно выполнятся следующее соотношение , т.е. выходной знак не зависит от состояния, а зависит только от входных знаков. Это свойство автомата касается функции выхода. Это ограничение приводит к следующим выводам, которые приводится в теореме 4.1.
Теорема 4. 1. О комбинационном автомате
Утверждение: любой комбинационный автомат эквивалентен автомату Мили с одним состоянием или автомату Мура с состояниями, где — количество знаков входного алфавита.
Доказательство:
A) пусть задан произвольный автомат.
, , ( где ) такой, что и
выполняется равенство , т.е. является комбинационным.
B) Доказательство осуществим путем минимизации произвольного автомата. Для этого рассмотрим некоторую строку — строка входного алфавита, длины Покажем, что любые два состояния у комбинационного автомата неотличимы друг от друга по индукции:
Шаг 1:Базис индукции.
Пусть задана строка:
Тогд получим:

Шаг 2::Предположение.
Пусть длины строки равна и известно что,

Шаг 3: Индуктивный переход.
Покажем, что , где , но таких, что выполняется предположение индукции:

, где — то состояние, в которое перейдёт автомат, будучи запущен из состояния q c входной строкой ;

Исходя из предположения индукции ( шаг 2 ) и свойства комбинационного автомата заключаем, что .
C) Из пункта В, заключаем, что все состояния комбинационного автомата попарно неразличимы, что если они попадают в один и тот же класс эквивалентности при минимизации автомата, то алгоритм Мили не расщепляет состояния или же классы эквивалентности, при минимизации не изменяются.
D) Таким образом, чтобы узнать число состояний комбинационного автомата необходимо знать начальное приближение классов эквивалентности.
Т.к. автомат комбинационный, т.е. для ,

То для каждого состояния столбец выходных знаков будет одинаков.
A\Q q1 … qi … qn
a1 /bj … /b2 … /b1

Последнее означает, что при использовании алгоритмов Мили, полученное начальное приближение классов эквивалентности состоящее из одного множества, куда включены все состояния автоматов.
Вывод: Комбинационный автомат может быть минимизирован; в результате чего получаем неотличимый от него автомат с одним состоянием.
Представим автомат в виде таблицы минимизированного комбинационного автомата:
A\Q q
a1 q/b1
aj q/bj
am q/bm
Множество состояний сократилось до одного состояния q:

Тогда значение q можно опустить:

В результате получаем таблицу истинности дискретной функции.
A\Q q
a1 b1
a2 b2
aj bj
am bm
E) Покажем сколько будет иметь состояний неотличимый от автомата К, автомата Мура.

Из теоремы ( О существовании автомата Мура) получим:

где n – число состояний, а m – число входных знаков:

Доопределим состояние выхода автомата для начального состояния таким образом, чтобы совпало с выходным знаком в некотором состоянии в результате минимизации автомата Мура, будем иметь не более чем m состояний .
Вывод: В общем случае комбинационный автомат с задержкой на один такт эквивалентен автомату Мура не более, чем на m состояний.
F) Определим более точное число состояний автомата Мура.
Qm
A
Таблица автомата Мура имеет следующий вид:
Несложно заметить из приведённой таблицы, что число состояний автомата Мура будет равно числу выходных знаков т .е. .
Поясним теорему при помощи примера:
Пример:
Q
A 1 2 3
2/0 1/0 2/0
3/1 3/1 2/1
1/0 2/0 1/0
Задан исходный комбинационный автомат при помощи таблицы:
Так как знак на выходе автомата не зависит от его состояния и определяется только входным знаком, то в результате минимизации автомата получим:
A Q/B
a 1/0
b 1/1
c 1/0
Если удалить состояние из таблицы получим:
Построим неотличимый от исходного минимальный автомат Мура:
Откуда видно, что ожидаемое количество состояний автомата не 3 – количество входных знаков, а 2 – количество выходных знаков исходного комбинационного автомата.