Способы описания конечных автоматов

Для описания конечных цифровых автоматов можно использовать стандартные (автоматные) языки и начальные языки.

Стандартные или автоматные языки описания.

Они описывают функции переходов и выходов в явном виде, а именно в виде:

Таблиц переходов и выходов;

Из определения автомата следует, что его всегда можно задать таблицей с двумя входами, содержащей m строк и n столбцов, где на пересечении столбца q( состояния автомата) и строки а (входные сигналы) стоят значения функций φ(l) (a_i,q_j) (функция переходов); \|/ (m )(a_i,q_j)(функция выходов).

Таблица 1

2) графа, представляющего наглядно функции l и m..

Другой способ задания конечного автомата — графический. При этом способе состояния автомата изображают кружками, в которые вписывают символы состояний q_j (j= 1,..., п). Из каждого кружка проводится m стрелок

( ориентированных рёбер) взаимно-однозначно соответствующих символам входного алфавита X(V). Стрелке, соответствующейбукве а_i X и выходящей из кружка q_j Q(S), приписывается пара (а_{i ,}\|/ (a_i,q_j) , причем эта стрелка ведет в кружок, соответствующий φ (a_i,q_j)

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

Автомат Мура

Абстрактный автомат Мура это частный случай автомата Мили (4), когда выходной символ зависти только от состояния автомата, а именно функция выходов автомата Мура:

w=m(s) (5)

Для каждого автомата Мили можно построить эквивалентный автомат Мура, реализующий точно такой же алфавитный оператор. Пусть A = <V,W,S,l,m,s(0)> автомат Мили. В качестве состояний эквивалентного автомата Мура возьмем пары . Тогда функция выходов эквивалентного автомата Мура

, (6)

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

. (7)

Задание конечного автомата системой булевых функций

Третий способ задания конечного автомата А = (X;Q;Y; φ ;\|/), заданного таблицей или диаграммой Мура, состоит в определении системы булевых функций.

X-входной алфавит;

Q-множество состояний автомата;

Y-выходной алфавит;

φ -функция перехода;

\|/-функция выходов.

Изложим алгоритм этого способа задания.

1.Находим числа k, r, s, удовлетворяющие условиям 2^k-1 < т< 2^k;
2^r-¹ < п ≤ 2^r; 2^s-¹ <p≤ 2^s, где m = |Х|; n = |Q|;p = |Y|.

Очевидно, что k,r, s соответственно равны числу разрядов в двоичном представлении чисел т, п, р. Например, если т — 5, п = 17, р = 3, то k= 3, r= 5,s = 2.

2. Кодирование состояний входных и выходных символов исходного
автомата.

Каждому q_j Q взаимно-однозначно ставим в соответствие двоичную последовательность длины r — двоичный код = z₁z₂z_r. Аналогично каждому а_i X и b_k Y ставим взаимно однозначно в соответствие двоичные последовательности =x₁x₂x_k; =y₁y₂y_s.

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

.

3.Составляем следующую таблицу:

Эта таблица содержит k + r + r + s столбцов и 2^k+r строк. В первых k + r столбцах выписаны все наборы длины k + r. Каждый такой набор соответствует паре ( ), где -возможный код некоторого состояния, код входного символа.

4.Заполнение последних столбцов в таблице (предыдущий шаг).

Для каждой пары (a_i,q_j), где а_i X; q_j Q, находим код и . По таблице автомата (или диаграмме Мура) определяем и \|/(а; q) = Y. Затем находим код = '₁ '₂... ',. и код .

В строку таблицы соответствующую набору

дописываем набор

5. Определение системы булевых функций.

После выполнения предыдущего шага может оказаться, что все строки в таблице заполнены. Это произойдет в том случае, если хотя б одно из чисел m, n не является степенью 2. Таким образом, функции окажутся не полностью определенными – на некоторых наборах их значения не определены. Тогда мы их доопределяем произвольным образом. Как правило, доопределение функций проводят так, чтобы получившиеся полностью определенные функции удовлетворяли тем или иным условиям оптимальности, например представлялись минимальными ДНФ.

После выполнения этого шага исходный автомат будет задавать системой полностью определенных булевых функций

3.2 Начальные языки.

Они описывают автомат на поведенческом уровне. К начальным языкам относятся:

1) языки логических схем и граф схем алгоритмов;

2) язык регулярных выражений алгебры событий;

3) формальные и автоматные грамматики.

Если задано описание (4) полностью определенного автомата в стандартной форме, то для любого начального состояния автомата s(0) и последовательности входных символов v(0)v(1)v(2)…v(t) можно вычислить реакцию автомата в виде последовательности выходных символов w(0)w(1)…w(t).

Примеры.

Пример 1. Автомат ПРОДАВЕЦ газет получает монеты достоинством в 1 рубль и 2 рубля. Если сумма монет равна 3 рублям, то автомат выдает газету. Если сумма больше 3 рублей, то автомат возвращает все деньги. Введем обозначения входных и выходных символов и состояний автомата.

Входные символы:

v₁ - опущена монета достоинством 1 рубль;

v₂ - опущена монета достоинством 2 рубля.

Выходные символы:

w₁ - сообщение "Принята сумма 1 руб.";

w₂ - сообщение "Принята сумма 2 руб.";

w₃- выдача газеты;

w₄ - возврат денег.

Состояния автомата:

s₀ - принята сумма 0 руб. (начальное состояние);

s₁ - принята сумма 1 руб.;

s₂ - принята сумма 2 руб.

Функцию переходов представим таблицей 2, а функцию выходов - таблицей 3.

Этот же автомат можно задать в виде отмеченного орграфа, вершины которого соответствуют состояниям автомата, а дуги - переходам (рис.3).

Рис. 3

Ниже приведен пример реакции автомата ПРОДАВЕЦ на входную последовательность v₁v₁v₂v₂v₁v₂v₂v₁v₁v₁…:

t

…

v(t)

…

v1

v1

v2

v2

v1

v2

v2

v1

v1

v1

…

s(t)

…

s0

s1

s2

s0

s2

s0

s2

s0

s1

s2

s0

w(t)

…

w1

w2

w4

w2

w3

w2

w4

w1

w2

w3

…

Пример 2. Для рассмотренного выше автомата ПРОДАВЕЦ можно построить эквивалентный автомат Мура, характеризуемый таблицей переходов/выходов (табл 4).

Таблица 4

Новое состояние
Входной символ	Текущее состояние/выходной символ
v1 v2	s1v1 s2v1 s2v1 s0v1 s0v1 s0v1 s1v2 s2v2 s2v2 s0v2 s0v2 s0v2

На рис.4 представлен граф переходов/выходов автомата ПРОДАВЕЦ, соответствующий табл.4. Начальное состояние эквивалентного автомата Мура включает входной символ v(0). Поэтому приходится смещать поток входных символов: .

Пример 3. Обозначим состояние автомата Мура, соответствующее паре (s_i,v_j) автомата Мили через s_ij. Тогда реакция эквивалентно автомата ПРОДАВЕЦ на последовательность v₁v₁v₂v₂v₁v₂v₂v₁v₁v₁… будет:

t	…
	…	v1	v2	v2	v1	v2	v2	v1	v1	v1	…
	…	s01	s11	s12	s02	s21	s02	s22	s01	s11	s21
w(t)	…	w1	w2	w4	w2	w3	w2	w4	w1	w2	…

Пример 4.

Опишем поведение родителя, отправившего сына в школу. Сын приносит двойки и пятерки. Отец не хочет хвататься за ремень каждый раз, как только сын получит очередную двойку, и выбирает более тонкую тактику воспитания. Задавать авто­мат удобно графом, в котором вершины соответствуют состояниям, а ребро из со­стояния s в состояние q, помеченное х/у, проводится тогда, когда автомат из состо­яния s под воздействием входного сигнала х переходит в состояние q с выходной реакцией у. Граф автомата, моделирующего умное поведение родителя, представ­лен на рис. 5.

Рис. 5. Автомат, описывающий поведение «умного» отца

Этот автомат имеет четыре состояния {s0, s1, s2, s3} и два входных сигнала — оценки, полученные сыном в школе: {2,5}. Начиная с начального состояния s0(оно помече­но входной стрелкой), автомат под воздействием входных сигналов переходит из одного состояния в другое и выдает выходные сигналы — реакции на входы. Выхо­ды автомата {у0,..., у5} будем интерпретировать как действия родителя так:

y0: — брать ремень;

yl: — ругать сына;

у2: — успокаивать сына;

уЗ: — надеяться;.

у4: — радоваться;

у5: — ликовать.

Сына, получившего одну и ту же оценку — двойку, ожидает дома совершенно раз­личная реакция отца в зависимости от предыстории его учебы. Отец помнит, как его сын учился раньше, и строит свое воспитание с учетом его предыдущих успе­хов и неудач. Например, после третьей двойки в истории 2,2, 2 сына встретят рем­нем, а в истории 2, 2, 5, 2 — будут успокаивать. Каждая предыстория определяет текущее состояние автомата, при этом некоторые входные предыстории эквива­лентны (именно те, которые приводят автомат в одно и то же состояние): история 2, 2, 5 эквивалентна пустой истории, которой соответствует начальное состояние.

Текущее состояние автомата представляет все то, что автомат знает о прошлом с точки зрения его будущего поведения — реакций на последующие входы. Эта ис­тория в концентрированном виде определена текущим состоянием, и все будущее поведение автомата, как реакция его на последующие входные сигналы, определе­но именно текущим состоянием, но не тем, как автомат пришел в него.

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

Определим конечный автомат формально.

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

Таблица 5.

Таблица 5, а определяет функцию переходов так:

а табл. 5, б определяет функцию выходов : .(s0, 2) = у2; (s2, 5) = у3; ....