Абстрактный синтез конечных автоматов

Примеры абстрактного синтеза конечных автоматов

1) Поведение автомата задано словесным описанием

2) Синтез автомата для реализации вычислительной операции

Два этапа синтеза:

1) Абстрактный синтез конечного автомата (КА)

2) Структурный синтез КА

Абстрактный синтез конечных автоматов

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

Для проведения абстрактного синтеза рекомендуется использовать так называемый метод «черного ящика», с помощью которого определяются связи с внешней средой, то есть определяются входные и выходные сигналы.

Пример 1:

Осуществить абстрактный синтез автомата, который собирает подарочный набор к Международному Женскому Дню 8 марта.

Автомат - устройство со зрительным анализатором, собирающее различные вещи.

Содержимое набора - одеколон, духи, пудра.

M₁ - манипулятор для укладывания духов М₂ - --//-одеколона или пудры

М₃ - --//-закрытия коробки, сталкивания ее на уходящий конвейер и взятия

новой пустой коробки.

Сигналы управления

M₁ М₂ и М₃

1) Определить входной алфавит X.

П - пудра

О - одеколон

Д-духи

2) Определить выходной алфавит Y.

у₀ - сигнал «ждать»

y₁ - сигнал, управляющий манипулятором М₁

у₂ - --//--М₂

у₃ - --//--М₃

3) Определить алфавит состояний А, то есть определить те ситуации, которые автомат должен запоминать. Это, очевидно, наличие предметов в коробке.

Примечание: при конструировании автомата нужно вводить начальное состояние.

4) Построение таблицы переходов (F - функция переходов).

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

Приоритеты: П - 2², О - 2¹, Д - 2⁰.

5) Построение таблицы выходов (Ф - функция выходов).

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

Пример 2:

Сконструировать автомат, который бы распознавал некоторый двоичный пароль в последовательном канале связи. При наличии правильного пароля - сигнал «есть», при его отсутствии - сигнал «нет».

Метод «черного ящика»

«110» - пароль

1) Вектор входных сигналов X.

2) Вектор выходных сигналов Y.

у₀ - нет комбинации

у₀ - есть комбинация

3) Вектор состояний А.

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

a₁ - пришла первая единица «1»

а₂ - пришла комбинация «11»

а₃ - пришла комбинация «110»

4) Графическое описание автомата.

Граф Мура Граф Мили