Пусть задан некоторый конечный автомат К
Вопрос : Как представить автомат в виде автоматной сети, возможно состоящий из более простых автоматов, чем исходных ? 
Здесь Теория автоматов разделяется на две части:

1. алгебраическая;
2. комбинаторная.

1. Алгебраическая теория решения задач структурного синтеза в самой общей постановке , когда в качестве элементарного автомата используются автоматы произвольного вида (общего вида).
Доказано, что имея конечный автоматный базис т.е. конечное число элементарных автоматов, невозможно построить любой произвольный наперёд неизвестного вида автомат.
Вывод: При алгебраическом подходе нет функциональных автоматных базисов.
2. В комбинаторной теории в качестве автоматного базиса используется конечное число комбинационных автоматов. Позже будет доказано, что производный автомат может быть представлен в виде схемы из комбинационных автоматов и конечного автоматного базиса.
Теорема 4.2. О структурном синтезе
Утверждение: произвольный конечный автомат может быть реализован автоматной сетью, состоящей из двух комбинационных автоматов , и элемента задержки D на один такт с состояниями. — это такой автомат, который повторяет входные знаки с задержкой в один такт, а n — число состояний начального автомата.

Доказательство:
A) Определим автоматы ? , V , D:
Автомат — реализует функцию
Автомат — реализует функцию
Линия задержки на один такт D, повторяет входные знаки алфавита Q на выходе Q с задержкой на один такт.
— автомат Мура. , где — функция переходов повторителя входных знаков.
Очевидно комбинационный автомат срабатывает мгновенно и упорядоченность работы автомата K во времени определяется элементом задержки на один такт.
B) Покажем неотличимость исходного автомата от автоматной сети индукцией по длине входной строки.
шаг 1:Базис индукции.
Пусть задана строка:
Тогда для автоматов и , запущенных из состояния q и при подаче входного знака a, получим:

т.е. следующее состояние у автоматов одинаково.
шаг 2:Предположение.
Предположим, что
Пусть
Тогда очевидно, что и следующее состояние у автоматов одинаково.
Допустим у обоих автоматов будет одинаково.
шаг 3: Индуктивный переход.
Пусть длина строки

Таким образом мы показали, что выходные строки одинаковы.
Следующее состояние после приёма знака у автоматной сети будет соответствовать (совпадать) со следующим состоянием исходного автомата.
C) Вывод: Т.к. для любого состояния исходного автомата мы нашли неотличимые от него состояния автоматной сети, то исходный автомат неотличим от автомата сети, если автоматная сеть и исходная сеть запускается из соответствующих состояний , что и требовалось доказать.
Замечание: При доказательстве теоремы использовался общий вид автомата ( автомат Мили ). Последнее означает, что теорема справедлива для автоматов частного вида:
синхронного и автомата Мура.
Если исходный автомат асинхронный, то элемент памяти ( элемент задержки D ) тоже должен быть асинхронным.
Действительно, если исходный автомат К – асинхронный, то как и для автоматной сети — изменение знака на входе приводит к изменению состояния на входе и выходе автомата . Происходит изменение входного знака происходит на элементе задержки, который через время задержки ? повторяет входной знак на выходе, что является новым состоянием автомата. Это состояние может в свою очередь привести к изменению как выходного знака, так и следующего состояния, но т.к. автомат асинхронный следующее состояние совпадает с ранее вычисленным.
В этом случае элемент задержки на один такт может быть не использован в схеме.

Для реализации произвольного автомата в виде схемы из комбинационных автоматов, необходим в общем случае элемент задержки на один такт, который по своему определению является автоматом с несколькими состояниями. Из предыдущего замечания следует, что такие автоматы могут быть реализованы, как асинхронные автоматы, не содержащие элемента задержки.
Вывод: для реализации произвольного автомата необходимо уметь реализовать, только комбинационный автомат т.к. элемент памяти может быть представлен в виде асинхронного автомата, не содержащего элемента задержки