Самый отдаленный пункт… к чему-нибудь да близок, а самый близкий – от чего-нибудь да отдален.
Козьма Прутков.
В данном разделе в отличие от предыдущего мы займёмся теоретической реализацией конечных автоматов при помощи логических элементов.
Тема 4.1. Сети из автоматов
Определение1: Автоматной сетью называется соединение автоматов, осуществляемое таким обра¬зом, что они функционируют согласованно, и образуют новый автомат. Такой подход, при котором автомат рассматривается как совокупность соединенных автоматов, мы раньше называли микроподходом. До сих пор автоматы рассматривались нами макроподходом, т.е. мы описывали его не вникая, из чего он состоит.
Пусть дан автомат, на входных каналах которого поступают алфавиты , а на выходе получаем алфавиты ,и множеством состояний .
Количество входных и выходных каналов у КА можно расширить.

Представим такой автомат как конечный автомат
Входные алфавиты являются декартовым произведением алфавитов
Ошибка! Объект не может быть создан из кодов полей редактирования.,
а выходные алфавиты также являются декартовым произведением алфавитов
Определение2: Сетью из автоматов (автоматной сетью) называют соединения конечных автоматов таким образом, что выход одного автомата служит входом для другого и они функционируют согласованно, то есть изменяют свои состояния в одни и те же дискретные моменты времени.
Основные виды соединения автоматов
Возможны различные соединения абстрактных автоматов, когда на вход одного из них подаются знаки с выхода другого, а выход, служит входом для других автоматов, при этом функционирование автоматов согласованно во времени (синхронизировано).
Существует три вида соединения автоматов:
1. Параллельное;
2. Последовательное;
3. С обратной связью.
Произвольную автоматную сеть можно получить путем этих соединений. Рассмотрим каждое из них.
1) Параллельное соединение автомата с раздельными входами.
Пусть заданы два конечных автомата .

Соединим их попарно с раздельными входами и получим новый автомат К, представленный в следующем виде:

У полученного автомата входной алфавит будет являться декартовым произведением входных алфавитов .Также поступаем с множеством состояний и выходными алфавитами и представим в следующем виде:

Тогда функция переходов примет вид:

где: — состояние автомата К,
— состояния первого исходного автомата
— состояния второго исходного автомата

— входные знаки первого канала, где
— входные знаки второго канала, где
Учитывая предыдущее, функция отметок примет вид:

где: — функция отметок первого исходного автомата, а
— функция отметок второго исходного автомата.
Также получаем произведение состояний и произведение знаков
2) параллельное соединение с общим входом
Автомат из пункта 1 можно упростить, если на входы автоматов и подаются одинаковые знаки.

В результате получили автомат с общим входом.
3) последовательное соединение

Можно ослабить условие и потребовать, чтобы , в этом случае из автоматного графа надо удалить все дуги из множества . Если окажутся изолированные вершины, то и они могут быть удалены из описания автомата.
a) — автомат Мили, т.е. выходной знак появляется быстрее, чем меняется состояние.

Пусть состояние автомата — есть , где , тогда для получим:

где — входной знак автомата ,
а и состояние автоматов и в следующий момент времени.

a) Пусть — автомат Мура.
— автомат Мили.

A,Q,B – тоже, что и в пункте (а).
Состояние:

Подставим вместо

Следующее состояние зависит как от предыдущего, так и от состояния предшествующего предыдущему .
4) с обратной связью:
Соединение с обратной связью предполагает, что выход автомата соединяется с его входом. Предполагается, что есть автомат имеющий следующий вид:

Входным алфавитом у этого автомата будет являться декартовым произведением входного алфавита и выходного алфавита .

Если обратную связь поместить внутрь автомата К, то входной алфавит будет являться входным алфавитом , а множество состояний увеличивается до декартового произведения .

Функция отметок будет изменена и примет вид
Здесь возможны два случая, когда автомат — синхронный и -асинхронный автоматы.
Синхронный автомат – когда существуют состояния не устойчивые по входным знакам. Т.е. для синхронного автомата следующее состояние будет зависеть как от входного знака , так и от вх.(вых.) знака , с задержкой на один такт.

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

Для представления любой автоматной сети достаточно трех видов соединения.
Пример : Попытаемся упростить автоматную сеть при помощи трёх видов соединений и привести её к одному конечному автомату:

Пример: Синхронный автомат с обратной связью,
Имея абстрактный автомат, построить описание синхронного автомата с обратной связью.

Пусть дан автомат
Где входной алфавит- А = { 0,1 },
а выходной алфавит B = { 0,1 ).
Построим исходную автоматную таблицу

Изобразим граф исходного автомата
Состояние2–не устойчиво по входному знаку 0b (переходит из. Ошибка! Объект не может быть создан из кодов полей редактирования., и изОшибка! Объект не может быть создан из кодов полей редактирования. ).
Построим итоговую таблицу для автомата с обратной связью:
B
A 1a 1b 2a 2b 3a 3b
0 1a/a 2b/b 1a/a 3a/a 2b/b 1b/b
1 3a/a 2a/a 1b/b 2a/a 3a/a 1b/b
Пример: Рассмотрим асинхронный автомат:
Построим исходную автоматную таблицу
Построим итоговую таблицу для автомата с обратной связью:
B
A 1/a 2/b 3/a
0 1/a 2/b 1/a
1 3/a 2/b 3/a

Изобразим граф исходного автомата:
Вывод: в результате мы построили асинхронный автомат т.к. все состояния устойчивы по входным знакам.
Способы введения времени в автоматную сеть
Существует три способа введения времени в автоматную сеть:
a) синхронный способ – когда вводится шкала времени, которая делится на отрезки одинаковой длины (такты), также нумеруют, начиная с 0.
• Длина такта (длительность такта) принимается за единицу времени. Входная строка рассматривается как последовательность знаков сменяемых с каждым тактом.
• Автоматные функции реализуются с задержкой в один такт. в свою очередь зависит от вида автомата (Мура или Мили) будет иметь .
• Синхронизация работы автомата в автоматной сети достигается за счет внешних синхронизирующих часов (источник синхронизации). Согласованная и одновременная работа автоматов в сети достигается за счёт использования одного и того же источника синхронизации.
b) Асинхронный способ. При асинхронном способе согласованная работа автоматов достигается изменением входных знаков, т.е. моменты функционирования автомата задаются изменением знака на входе. Мы ввели понятие асинхронного автомата.

c) Апериодический способ синхронизации – реализуется за счет подбора временных характеристик среды распространения знаков между автоматами и времени функционирования автоматов.

Каждый из этих автоматов функционирует, какое то время ?t и вносит задержку. Очевидно, для того чтобы автоматы работали синхронно, нужно подобрать временные характеристики так, чтобы добиться согласованности работы системы( т.е. в данном случае для согласованной правильной работы сети необходимо равенство времени задержки автоматов и ).