Определение: Элемент задержки на один такт, используемый в теореме о структурном синтезе автомата КА, — является асинхронным автоматом.
Доказательство:
A) В теореме 4.2. мы показали, что для автомата , элемент задержки может быть представлен следующей автоматной таблицей:
Q
Q q1/ q1 q2/ q2 … qi/ qi … qn/ qn
q1 q1 q1 … qi … qn
q2 q2 q2 … qi … qn
… … … … … … …
qj qj qj … qi … qn
… … … … … … …
qn qn qn … qn … qn
B) Из таблицы видно что, все состояния автомата устойчивы по всем входным знакам, ведущим в это состояние.
Рассмотрим некоторые состояния qi, в это состояние ведут дуги от всех других состояний qj, очевидно помеченные знаком qi. Перейдя в состояние qi , при получении того же входного знака, автомат переходит в это же состояние, т.е. каждое состояние элемента памяти устойчиво по всем входным знакам, и представляет собой асинхронный автомат, функционирующий в дискретные моменты времени. Т.е. знак на входе появляется на выходе в следующие моменты времени функционирования автомата.
Теорема доказана.
Пример: Синтез асинхронного автомата.
Замечание к теореме. В соответствии с последними двумя теоремами получили вывод:
Для синтеза произвольного автомата необходимо уметь реализовать комбинационный и асинхронный автоматы. Ни тот, ни другой для своей реализации не требует элемента задержки на один такт.
Дан асинхронный автомат .
Представим его в виде автоматной сети
Представим в виде графа

На этом рисунке представлен вид автоматной сети.

Задаём ? и ? в виде комбинационного автомата:

Выбираем автоматный базис, реализующий функционально полную систему операций в булевой алгебре: ? = { &, V, – } N2 = { 0, 1 }
Q ,Q+ 1 2 3

00 01 10
Задаём код
А a b c

00 01 10
Задаём таблицу истинности для булевых функций, описывающих работу автомата с учётом кодирования алфавитов.
A Q B Q+

Представляем функции из таблицы в виде выражений в функционально полном базисе .

Рисуем схему искомого автомата, используя логические элементы выбранного автоматного базиса.