Раздел 3. Абстрактные и микропрограммные автоматы

Тема 3.1. Определение абстрактного автомата. Соединение двух автоматов:

последовательное, параллельное и с обратной связью.

Абстрактный автомат (АА) задается шестеркой (шестикомпонентным вектором):

- множество (алфавит) состояний;

- множество (алфавит) входных сигналов;

- множество (алфавит) выходных сигналов;

- функция переходов автомата. Функция паре ставит в соответствие некоторое состояние :

функция выходов автомата. Функция паре ставит в соответствие некоторый выходной сигнал

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

Автомат называется конечным, если конечны множества , , .

В дальнейшем будем иметь ввиду только конечные автоматы.

Автомат называется детерминированным, если для всех пар функция имеет единственное значение. В дальнейшем будем иметь ввиду только детерминированные автоматы. Наряду с детерминированными существуют автоматы недетерминированные и стохастические.

В рамках курса будем рассматривать как синонимы следующие термины:

• алфавит, буква, символ;

• слово, цепочка.

С мысл вышеприведенных терминов очевиден и не требует формальных определение.

АА имеет один вход и один выход:

Автомат работает в дискретном времени, принимающем значения

Всегда

В момент времени автомат находится в состоянии . На его вход поступает входной символ . В качестве реакции на входной символ автомат выдает некоторую букву выходного алфавита: . Затем в соответствии с функцией перехода переходит в следующее состояние: .

На этом заканчивается один цикл работы автомата.

Последовательность символов входного алфавита: задает входное слово (слово входного алфавита).

Последовательность символов выходного алфавита задает выходное слово (слово выходного алфавита).

Работа АА состоит в преобразовании слов входного алфавита в слова выходного алфавита.

В АА отвлекаются от внутренней структуры автомата, рассматривая его как “черный ящик”. При этом основное внимание уделяется поведению автомата относительно внешней среды. В качестве элементов, связывающих автомат с внешней средой, выступают входные и выходные слова.

Введение состояний в описание устройства позволяет запоминать и учитывать предысторию поведения автомата. Это дает возможность строить устройства, которые на одни и те же входные сигналы в разные моменты времени реагируют по-разному.

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

Основными видами соединений 2х автоматов являются:

• параллельное;

• последовательное;

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

Начальное состояние не выделено.

- функциональный преобразователь (автомат без памяти).

.

Результирующий автомат

1. - множество всевозможных пар вида ;

2. - входной алфавит автоматов и ;

3. - заданное отображение

4. Функция переходов определяется следующим образом:

, или по другому:

5. Функция выходов определяется следующим образом:

, или иначе:

.

Пример:

Построим автомат .

Построение таблиц:

Пример

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

, у которого:

1) , или

2)

3)

4) , определяется следующим образом:

или

5) , определяется следующим образом:

или

Пример:

- тот же, что при параллельном соединении.

Результирующим автоматом будет автомат , у которого

1)

2)

3)

4)

Здесь, например,

5)

Соединение с обратной связью

- автомат без памяти – функциональный преобразователь, реализующий отображение .

Здесь хотя бы один из автоматов должен быть типа Мура.

Пусть - автомат модели Мура. Тогда результирующий автомат , у которого:

1) , или

2)

3)

4) , определяемая следующим образом:

или

5) , определяемая следующим образом:

или

Пример:

;

Решение