Конечный автомат

ft(h1(as), h2(qs))=h2(fs(as, qs)),

gt(h1(as), h2(qs))=h3(gs(as, qs)),

т, е. операции отображения алфавитов автомата S в T и действия функций f и g коммутативны.

Однако, установление гомоморфизма недостаточно для определения эквивалентности автоматов

Взаимно-однозначный гомоморфизм автоматов S и T называется изоморфизмом и он устанавливается введением дополнительной тройки функций отображения: h'1:At®As; h'2:Qt®Qs; h'3:Vt®Vs  и выполнением дополнительных условий

fs(h'1(at), h'2(qt))=h'2(ft (at, qt)),

gs(h'1(at), h'2(qt))=h'3(gt (at, qt)).

 

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

Пусть S и T - два автомата с одинаковыми входным и выходным алфавитами. Состояние q автомата S и состояние r автомата T называются неотличимыми, если для любого входного слова u S(q, u)=T(r, u). В частности, если T=S, то речь идет о неотличимых состояниях одного и того же автомата S.

Автоматы S и T называются неотличимыми, если для любого состояния q автомата S найдется неотличимое от него состояние r автомата T и, наоборот, для любого r из T найдется неотличимое от него q из S. Неотличимость автоматов означает, что их возможности по реализации преобразований входной информации в выходную информацию совпадают. Неотличимость автоматов называют эквивалентностью.

Переход от автомата S к эквивалентному автомату называется эквивалентным преобразованием автомата S.

Эквивалентные преобразования  используются при минимизации КА.

Минимизация КА включает:

• определение и исключение недостижимых состояний;
• определение и исключение эквивалентных состояний.

1.3.2 Недостижимые состояния  КА

Определение множества недостижимых состояний КА основано на следующей аксиоме и свойстве.

Аксиома: начальное состояние КА всегда достижимо.

Свойство: если достижимо состояние, находящееся в левой части таблицы переходов (ТП), то достижимы и состояния находящиеся в правой части таблицы для данной строки.

Алгоритм определения недостижимых состояний включает в себя следующие шаги:

1. Формируется множество  достижимых состояний D, куда включается начальное состояние КА (на основании аксиомы).

2. Для каждого состояния  из множества D выделяется строка ТП и осуществляется обновление множества D за счет элементов  правой части выделенной строки.

3. Повторяется п.2 до тех  пор, пока не будут обработаны все состояния из множества D и пока происходит обновление множества D.

4. Определяется множество  недостижимых состояний N как разность множества Q всех состояний КА и множества достижимых состояний

N = Q – D.

 

 

 

 

 

Рассмотрим работу алгоритма для КА, заданного таблицей 1.6:

Таблица 1.6

Q \ A	1	2	1. Формируется множество достижимых  состояний D, куда включается начальное состояние КА (q2) D = { q2}. 2. Выделяется 2 строка и обновляется  множество D за счет элементов правой части строки D = D + {q1, q4}={ q2, q1, q4}. 3. Повторяется п.2. для элемента q1 из D D = D + {q3} = {q2, q1, q4, q3}.
q1	q4	q3
q2	q1	q4
q3	q2	q1
q4	q3	q2
q5	q3	q4

 

4. Повторяется п.2. для элемента q4 из D  (обновление D при этом не происходит)

D = D + {  } = {q2, q1, q4, q3}.

5. Повторяется п.2. для элемента q3 из D (обновление D при этом не происходит)

D = D + {  } = {q2, q1, q4, q3}.

6. Так как все элементы из  множества D обработаны и обновление D не происходит, то пределяется множество недостижимых состояний

N = Q – D = {q1, q2, q3, q4, q5} - {q2, q1, q4, q3} = {q5}.

1.3.3 Эквивалентные состояния  КА

Задача минимизации числа состояний автомата (минимизация автомата) формулируется следующим образом: среди автоматов, эквивалентных S, найти автомат с наименьшим числом состояний - минимальный автомат.

Наиболее известным алгоритмом нахождения эквивалентных состояний является алгоритм Мили. Его суть состоит в том, что состояния автомата на каждом шаге разбиваются на классы эквивалентности, причем разбиение на следующем шаге будет получаться расщеплением некоторых классов предыдущего разбиения. (Отметим, что шаги алгоритма в данном описании вовсе не элементарны. Это скорее блоки.)

 Рассмотрим реализацию  алгоритма Мили:

1. Необходимым условием  эквивалентности состояний автомата  является тот факт, что при воздействии одинаковых ai сигналов в этих состояниях на выходе автомата получаем также одинаковые сигналы v.

 

 

 

 

 

 

 

В таблице 1.7 приведено описание КА.

 

Таблица 1.7                                                       Таблица 1.8  

Q \ A	a1	a2		Q \A	a1	a2
q1	q3, v2	q1, v1		q1	q1, v2	q1, v1
q2	q4, v2	q1, v1		q2	q3, v2	q1, v1
q3	q1, v2	q3, v1		q3	q1, v1	q3, v2
q4	q3, v1	q4, v2

 

Из таблицы следует, что при действии сигнала а1 в состояниях q1,q2, q3 на выходе будет одинаковый сигнал v2. Действие в этих же состояниях сигнала а2 приведет к появлению на выходе одинакового сигнала v1.

Следовательно, на первом шаге выделяется класс эквивалентности, включающий первые три строки таблицы 6 (состояния q1, q2, q3).

Этот класс отражен на рис.1.2 соответствующими  ячейками, внутри которых отмечены состояния, в которые переходит КА из потенциально эквивалентных состояний. В тех случаях, когда КА переходит в состояния, аналогичные предыдущим, в ячейке запись отсутствует, что имеет место для состояний (q1 q3).

Состояния (q1 q4),(q2 q4) и (q3 q4) не эквивалентны, так как для этих состояний для одинаковых входных сигналов имеют место различные выходные сигналы КА. Эти ячейки перечеркнуты (X1).

q2	q3 q4     X2
q3		q1 q4     X2 q1 q3
q4	X1	X1	X1
	q1	q2	q3

 

рис.1.2

На втором шаге анализируется информация сформированной таблицы. Так как состояния (q3 q4) не эквивалентны, то ячейка (q1 q2) с записью этих состояний перечеркивается. Это же выполняется для ячейки (q2 q3) с записью не эквивалентных состояний (q1 q4) (X2). Таким образом, эквивалентными состояниями являются только (q1 q3). Это обусловлено тем, что только из состояний q1 и q3 автомат переходит вновь в эквивалентные состояния, что не имеет места для любых других состояний. Таким образом, из класса эквивалентности, полученного на 2-ом шаге для определения состояний эквивалентного автомата можно выбрать одну строку (1-ю или 3-ю). Выбираем 1-ю строку, добавляем к ней 2-ю и 4-ю строки и переобозначаем состояния. В результате получим КА, описываемый таблицей 1.8.

 

1.4 Структурный синтез  конечных автоматов

1.4.1 Кодирование состояний конечного  автомата

После минимизации числа состояний автомата может быть определено

число элементов памяти, необходимое для реализации состояний КА.

Для двоичных элементов памяти их минимальное число kмин определяется выражением

kмин ³ log2 N ,

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

Кодирование внутренних состояний КА заключается в сопоставлении

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

Наиболее распространенным элементом памяти является RS - триггер, элемент с двумя устойчивыми состояниями (рисунок 1.3) и c соответствующей таблицей переходов (X - запрещенное состояние)

Число состояний КА (рисунок 1.1) N=2, следовательно,  kмин=1, т.е. для кодирования состояний КА требуется один элемент памяти. Тогда состояние q1 закодируем кодом 0, а состояние q2 -кодом 1.

1.4.2 Построение таблицы канонических уравнений

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

Каноническая таблица

q	qt-1	qt	S	R	V
0	0	1	1	0	1
1	0	0	0	-(1)	0
0	1	1	-(1)	0	0
1	1	0	0	1	1

Доопределяем таблицу для позиций (-) так, чтобы не изменить смысл функционирования КА:

Во второй строке проставляем вместо (-) логическую 1. Это значит, что если на триггер, находящийся в "0" состоянии, на вход S подать 0, а на вход R - 1, то его состояние не изменится.

На этом же основании доопределяем позицию (-) в третьей строке. Выделив конституенты единицы для сигналов S, R и V, получаем в дизъюнктивной нормальной форме (д.н.ф.) уравнения 

        S = -1 + qt-1,  R = -1 + qt-1,  V = -1 + qt-1.

Упрощаем выражения   S = ,    R = ,    V = -1 + qt-1.

Полученные выражения описывают функциональную схему КА (рисунок 1.4).

 

1.5 Структурный анализ  конечных автоматов

Задача анализа КА заключается в получении его таблицы переходов-выходов и графа переходов по функциональной схеме. В результате решения задачи анализа может определиться правильность построения схемы КА, соответствие его характеристик требуемым значениям. Исходными данными для анализа КА является его функциональная схема и таблицы переходов элементов памяти.

Задача анализа КА может быть решена в следующей последовательности:

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

2. Получение функций возбуждения  памяти и функций выходов.

3. Построение таблицы  возбуждений.

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

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

6. Построение абстрактной  таблицы переходов-выходов и графа  переходов КА.

Выполняем функциональный анализ схемы КА (рисунок 1.4). В КА используется RS-триггер (рисунок 1.3) с  соответствующей таблицей переходов.

На рисунке 1.4 блок 1 изображает схему возбуждения (управления памятью), а блок 2 - схему выходов.

Строим функции возбуждения памяти и функцию выходов

S =

,    R = ,    V = -1 + qt-1.

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

Таблица возбуждений                             Таблица переходов

A/Q	0		1				A/Q	0	1
	S	R		S	R
0	1	0		1	0		0	1	1
1	0	1		0	1		1	0	0