Технические дисциплины - ПППСМ
2.3. Способы задания абстрактного автомата (абстрактный язык).

 

Общая теория автоматов делится на абстрактную и структурную теорию ЦА.

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

Понятие абстрактного автомата, общие понятия автоматов Мили и Мура относятся к абстрактной теории ЦА.

Рассматриваемые способы задания АА, которые нужны для минимизации числа состояний автомата.

Задать автомат, значит описать все компоненты вектора S = (A, Z, W, δ, λ, a1).

Наибольшее распространение получили следующие способы задания автомата:

  1. Табличный
  2. Графический

Они нужны для описания поведения АА.

Задание автомата Мили.

1. Табличный.

Автомат задается с помощью двух таблиц: таблицы переходов и выходов.

Пусть автомат принимает состояние A = {a1, a2, a3}при подаче входного алфавита Z = {z1, z2}; W = {w1, w2}.

 

Таблица 2.1. Таблица переходов δ.                 Таблица 2.2.  Таблица выходов λ.

am

zf

a1

a1

a3

 

 

am zf

a1

a2

a3

z1

a2

a3

a3

 

 

z1

w2

w1

w2

z2

a3

a2

a1

 

 

z2

w2

w1

w1

Под воздействием z1 автомат из начального состояния a1 перейдет в a2. Функция δ задается для каждого автомата своя и описывает его поведение. В таблице переходов на пересечении столбца am и строки zf указывается новое состояние as, в которое автомат перейдет под воздействием zf. На пересечении столбца am со строкой zf в таблице выходов ставится выходной сигнал wg = λ (am, zf)  в текущий момент времени.

Эти две таблицы можно совместить в одну – совмещенную таблицу переходов и выходов.

 

Таблица 2.3. Совмещенная таблица переходов и выходов.

am zf

a1

a2

a3

z1

a2

w2

a3

w1

a3

w2

z2

a3

w2

a2

w1

a1

w1

В частичном алфавите Мили на месте неопределенных состояний или выходных сигналов в таблице ставится прочерк.

Буквы am, zf, wg в таблицах – это изображения двоичных чисел.

Например: z1 = 00         w1 = 000

z2 = 01         w2 = 001

На этапе структурного синтеза ЦА можно перейти к кодированным таблицам переходов и выходов.

2. Графический.

Основан на представлении алфавита в виде ориентированного графа.

Граф автомата – это ориентированный граф, вершины которого соответствуют состояниям автомата, а дуги – переходам между ними. Дуга, направленная из am в as, задает переход в алфавите из состояния am в as. Если wg не определен, то на месте wg ставится прочерк. Если переход из am в as осуществляется под воздействием нескольких входных сигналов, то дуге присваиваются все входные и соответствующие им выходные сигналы.

 

Автомат Мили, показанный в совмещенной таблице, имеет следующий граф:

 

Задание автомата Мура.

1. Табличный.

Автомат Мура задается с помощью отмеченной таблицы переходов и выходов. В ней каждому ее столбцу приписывается не только состояние am, но еще и выходной сигнал wg, соответствующий этому состоянию.

wg = λ (am)

Таблица 2.4. Отмеченная таблица переходов и выходов.

wg

w1

w2

w1

w1

am

zf

a1

a2

a3

a4

z1

a2

a3

a4

a4

z 2

a4

a1

a1

a1

A = {a1, a2, a3};

Z = {z1, z2};

W = {w1, w2}.

Автомат при воздействии входного сигнала z1 переходит из состояния a1 в a2 и вырабатывает w1.

Из таблицы видно, что в состоянии a3 автомат постоянно вырабатывает сигнал w1 и т.д. Эта особенность хорошо видна при графическом способе задания.

2. Графический.

Граф автомата Мура, соответствующий последней таблице.

 

Автомат из a2 под воздействием z1 переходит в состояние a3 и, находясь в a3, вырабатывает выходной сигнал w1. Около каждой вершины am проставляются в соответствии с отмеченной таблицей выходные сигналы wg. В начале дуги перехода указывается входной сигнал, вызывающий переход.

 



 

Добавить комментарий


Защитный код
Обновить