Соединение. Пример.

Абстра́ ктный автома́ т (в теории алгоритмов) — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии из множества возможных. На вход этому устройству поступают символы одного алфавита, на выходе оно выдаёт символы (в общем случае) другого алфавита.

Абстрактный автомат

Формально абстрактный автомат определяется как пятерка

Где S — конечное множество состояний автомата, X, Y — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, — функция переходов, — функция выходов.

Параллельное соединение:

Параллельное соединение

Пусть заданы два автомата Мили:

Параллельное соединение возможно, если только . Считаем также, что задано устройство , объединяющее выходы и реализующее функцию , представленную на рисунке 5.5. Для эквивалентного автомата Мили (рисунок.5.6) имеем выходной алфавит

множество состояний ,

функцию переходов

функцию выходов

и начальное состояние .

Пример 5. Пусть автоматы заданы таблицами 5.4 и 5.5 соответственно, функция таблицей 5.6. Считаем, что .

Результирующий автомат характеризуется совмещенной таблицей переходов/выходов (таблица 5.7).

11. Абстрактный автомат. Соединение двух автоматов последовательное.

Пример.(про АО см.10 вопр)

Соединение последовательно:

Последовательное соединение

Пусть задано последовательное соединение автоматов Мили (рисунок 5.7). Предполагается, что выходной алфавит совпадает с входным алфавитом

Тогда для эквивалентного последовательного автомата Мили имеем:

множество состояний ,

функцию переходов

и функцию выходов

Пример 6. Рассмотрим последовательное соединение автоматов из примера 5. Считаем, что . Тогда последовательное соединение характеризуется совмещенной таблицей переходов/выходов (таблица 5.8).

12. Абстрактный автомат. Соединение автоматов с обратной связью.