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

Алгоритм минимизации полностью определенного автомата (алгоритм Ауфенкампа – Хона):алгоритм заключается в разбиении всех состояний  на попарно непересекающиеся классы эквивалентных состояний и замене каждого класса одним состоянием. В результате получаем минимальный автомат, число состояний которого равно числу классов эквивалентных состояний, на которые разбиваются состояния исходного автомата. Рассмотрим автомат Мили. Два состояния  и  называются эквивалентными , если  для всех входных слов . , если  для вех входных слов  длины . Если условие не выполняется, то  и  эквивалентно различимы. Введенное понятие  - эквивалентности может использоваться для построения алгоритма разбиения множества  на непересекающиеся классы эквивалентных  и  - разбиение  на классы эквивалентных и  - эквивалентных состояний соответственно. Множество  несократимо, если  и  содержат одно состояние. Если имеются классы эквивалентов, содержащие более одного состояния, то все элементы могут быть исключены, кроме одного. Получим минимальный автомат.

1.  найти последовательно разбиения  множества  состояний автомата на классы одноэквивалентных, двуэквивалентных, …до тех пор, пока на  шаге  не окажется равным . Доказано, что при этом , то есть  - эквивалентные состояния являются эквивалентными. Максимальное число шагов процесса минимизации равно , где  – это мощность множества .

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

Последовательность:

a)  определить входной алфавит

b)  определить выходной алфавит

c)  задать начальное состояние  и соответствующую ему вершину графа автомата

d)  определить подмножество входных сигналов автомата, при наличии которых состояние  не должно меняться

e)  сформировать при вершине  петлю и пометить ее всеми входными сигналами, при которых состояние не меняется и соответствующими выходными сигналами

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

g)  провести анализ возможности совмещения каждого из введенных состояний  с имеющимися состояниями

h)  все состояния , для которых выделены эквивалентные, заменить эквивалентными

i)  для каждого нового состояния в графе сформировать новую вершину и провести

j)  для каждого состояния сформировать переход

k)  пометить все дуги  соответствующими наборами входных и выходных сигналов

l)  если все петли графа замкнуты и сформированы все переходы, перейти к пункту n), иначе к пункту m)

m)  выбрать новое состояние , для которого не сформированы все переходы и перейти к пункту d)

n)  конец

Структурная теория

Теория учитывает структуру входных и выходных сигналов автомата, а также его внутреннюю структуру. Основная задача – изучение композиции автомата (нахождение методов построения структурных схем сложных автоматов на основе композиции автоматов, являющихся более простыми и принадлежащих к заранее заданному конечному числу типов). Например, не учитываются переходные процессы, физические свойства надежности.

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

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

Под композицией элементарных автоматов понимают их объединение в систему совместно работающих автоматов. Для этого в системе элементарных автоматов  производят отождествление входных и выходных узлов, а также внешних входных и выходных узлов. После этого система автоматов превращается в схему автомата. Число его состояний – произведение всех чисел состояний . Состояниями автомата можно считать упорядоченный набор состояний автоматов . Предполагается, что все автоматы имеют один и тот же структурный алфавит и работают в одном и том же времени. Под структурным алфавитом понимают набор возможных входных сигналов, подаваемых на один структурный узел.