Тема 2. Абстрактный синтез конечного автомата

Задача абстрактного синтеза КА состоит в разработке математической модели на основании

заданного алгоритма функционирования автомата. Так как модель представляет собой кортеж А = (X, Y, S, f_y, f_s), то, очевидно, в процессе синтеза необходимо получить описания всех его компонентов. Достичь этого можно различными путями.

Множества X, Y, S могут быть заданы одним из известных в теории множеств способов (см. соответствующий раздел дисциплины «Дискретная математика»). Поскольку множества конечны, можно ограничиться простым перечислением их элементов, если мощности множеств невелики, или, например, указать порождающую рекурсивную процедуру, которая описывает соответствующее множество.

Для задания характеристических функций наиболее распространенными являются табличный и графический способы. Табличный способ состоит в построении таблицы переходов и выходов КА. Графический способ – в построении взвешенного орграфа переходов автомата.

Рассмотрим пример.

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

Автомат имеет два входа x₁, x₂ и один выход y. Если на входе x₂ сигнал меняется из 0 в 1, то на выходе формируется сигнал, равный сигналу на входе x₁. Если на входе x₂ сигнал переходит из 1 в 0, автомат выдает сигнал . В остальных случаях на выходе сохраняется ранее установленное значение. В начальный момент времени выходной сигнал равен 0.

Определим входящие в модель множества.

1. Так как входов два, причем существенно состояние только x₂, то множество входных сигналов можно ограничить только двумя элементами – парами вида (x₁, x₂):

X = {(x₁, 0), (x₁, 1)} или, для краткости, X = {x₁0, x₁1}.

Конкретизировать значения входной переменной x₁ нет необходимости, да и невозможно: из условия задачи вовсе не следует, что автомат работает в двоичной системе счисления.

2. Множество выходных сигналов очевидно следует из условия задачи:

Y = {0, x₁, }.

3. Элементы множества состояний должны фиксировать все шаги алгоритма. Если алгоритм представить в виде блок-схемы, то каждому операционному блоку, включая начальный, можно поставить в соответствие состояние автомата. Другой вариант: выходу каждого операционного блока сопоставляется отдельное состояние автомата. Блок-схема алгоритма работы заданного автомата выглядит следующим образом (рис. 2.1):

(s₀)

нет

да

нет

(s₁)

да

(s₂)

Рис. 2.1. Блок-схема алгоритма функционирования автомата

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

s₀ – начальное состояние, для которого примем x₁ – произвольное, x₂ = 0, y = 0;

s₁ – состояние, при котором x₁ – произвольное, x₂ переходит из 0 в 1, вырабатывается y = x₁;

s₂ – состояние, при котором x₁ – произвольное, x₂ переходит из 1 в 0, вырабатывается

Итак, S = {s₀, s₁, s₂}.

Построим граф переходов автомата (рис. 2.2):

Рис. 2.2. Взвешенный орграф переходов КА

Вершины графа переходов соответствуют состояниям. Дуга, направленная из вершины s_i в вершину s_j, задает переход КА вида:

Переход инициируется входным сигналом x_kÎX. На переходе формируется выходной сигнал y_mÎY. Поэтому весом дуги является пара «вход/выход»: x_k/y_m. В данном примере веса дуг представлены в формате x₁x₂/y.

Построенная по графу таблица переходов/выходов автомата показана на рис.2.3.

y(t)	s(t+1)
x(t) s(t)	x10	x11	x10	x11
s0		x1	s0	s1
s1	Øx1	x1	s2	s1
s2	Øx1	x1	s2	s1

Рис. 2.3. Таблица переходов/выходов КА

Строки таблицы соответствуют состояниям автомата, левая подтаблица отражает значения выходного сигнала в момент времени t для каждой пары «состояние – входной сигнал», правая подтаблица показывает, в какое состояние перейдет автомат в следующий момент времени из данного состояния под воздействием каждого значения входного сигнала.

Следует отметить, что выходной сигнал (т.е. функция выходов) зависит как от входного сигнала, так и от состояния автомата в момент времени t. Таким образом, построенная модель является автоматом Мили. Подчеркнем, что в автомате Мили выходной сигнал формируется именно на переходе КА из одного состояния в другое. ▄

В случае автомата Мура значение выходного сигнала в момент времени t определяется исключительно состоянием КА в этот момент времени (см. уравнения (2)). Поэтому при построении графа переходов обозначение выходного сигнала y_m приписывается вершине S_i^’, соответствующей состоянию, в котором этот выходной сигнал формируется. Дуга графа, инцидентная вершинам s_i^’ и s_j^’, задает переход КА Мура вида:

Весом дуги является значение входного сигнала, инициировавшего переход.

Например, автомат Мура, граф переходов которого представлен на рис. 2.4, имеет три состояния: s₀^’, s₁^’, s₂^’, вырабатывает выходной сигнал трех значений: y₀, y₁, y₂, а множество входных сигналов состоит из двух элементов: x₁, x₂.

Рис. 2.4. Пример взвешенного орграфа переходов автомата Мура

Таблица переходов/выходов автомата Мура имеет несколько иной вид. Например, для автомата на рис. 2.4 таблица выглядит следующим образом (рис. 2.5):

y(t)	y0	y1	y2
s’(t) x(t)	s0’	s1’	s2’
x1	s0’	s1’	s1’
x2	s1’	s2’	s0’

Рис. 2.5. Таблица переходов/выходов автомата Мура

Каждое значение выходного сигнала вырабатывается, когда автомат находится в соответствующем состоянии (столбцы таблицы). Под воздействием каждого входного сигнала автомат переходит в из текущего состояния s'(t) в s состояние s'(t+1) в соответствии с алгоритмом функционирования (строки таблицы). Таким образом, часть таблицы, выделенная двойной рамкой, есть s'(t+1).

Дата добавления: 2015-07-26; просмотров: 288; Нарушение авторских прав

Мы поможем в написании ваших работ!