Абстрактный и структурный синтез автомата Мура

ОГЛАВЛЕНИЕ

Алгоритм работы автомата

Глава 1 Абстрактный синтез автомата

Составление регулярных выражений

Разметка мест регулярных выражений

Первый этап минимизации

Составление отмеченной таблицы переходов

Второй этап минимизации

Глава 2 Структурный синтез автомата

Определение параметров схемы

Кодирование состояний

Построение кодированной таблицы переходов

Составление диаграмм Вейча

Определение типов используемых триггеров

Список литературы

Алгоритм работы автомата

На вход автомата поступает непрерывная последовательность букв и , составляющих входной алфавит X. На выходе автомата в дискретные моменты времени формируется последовательность букв е, , выходного алфавита У, причем сигнал выдается после пятибуквенных слов, начинающихся с , и продолжает выдаваться после каждой следующей буквы до тех пор, пока на вход автомата не поступят подряд четыре буквы , после поступления которых выдается сигнал у2. В остальных случаях автомат выдает пустую букву е.

Синтез автомата провести на RS-триггерах и логических элементах И-НЕ. Коэффициент объединения по входу равен четырём, коэффициент разветвления по выходу - четырём.

Глава 1. Абстрактный синтез автомата

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

Обозначим через Х=(, , ..., ,..., ) множество входных сигналов автомата, через У=(, , ...,,...,) - множество выходных сигналов, а через а=(,, ..., , ...,) - множество состояний, где - начальное состояние автомата. В рассматриваемом примере m=2, k=3 (число входных и выходных сигналов).

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

1.1 Составление регулярных выражений

Составим регулярные выражения и , включающие все слова, при поступлении которых автомат выдает буквы , и е соответственно.

Событие, включающее все пятибуквенные слова алфавита X, начинающиеся с букв записывается в виде выражения

.

Умножая это событие на событие { } ,которое включает все слова, оканчивающиеся на и не имеющие серии из четырех подряд идущих букв , получим событие S:

S=

Представленное в автомате буквой, получается путем умножения события S на слово , поскольку событиедолжно содержать все слова, оканчивающиеся четырьмя буквами , а автомат согласно алгоритму может выдать букву у2 только после буквы:

Событие, представленное в автомате пустой буквой е, записывается в виде:

1.2 Разметка мест регулярных выражений

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

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

36 36 36 36 36

1.3 Первый этап минимизации

Проведем минимизацию числа внутренних состояний синтезируемого автомата, уменьшив число индексов основных мест размеченного регулярного выражения.

Одинаковым индексами отметим те основные места регулярного выражения события S2, слева от которых стоят одинаковые буквы, перед которыми находятся предосновные места, отмеченные одинаковой совокупностью индексов. Из размеченного выражения следует, что одинаковым индексом можно отметить основные места с индексами:

0 1 2 3 4 2 3 4 2 3 10 2 12 13

40

36 36 36 36 36

1.4 Составление отмеченной таблицы переходов

По окончательному размеченному выражению составим отмеченную таблицу переходов автомата. Из размеченного выражения следует, что входной сигнал переводит автомат из состояний 0 и 40 в состояние 1, а сигнал из этих состояний переводит автомат в состояние 0. Аналогично определяются переходы автомата и из других внутренних состояний. Учитывая, что в состояниях 0,1,2,3,4,10,12,13,16 автомат выдает пустую букву е, в состояниях 5,8,11,14,17,20,23,26,27,28,29,32,36 автомат выдает букву , а в состоянии 40 выдает , получим следующую отмеченную таблицу переходов автомата (табл.1):

Таблица 1

1.5 Второй этап минимизации

Проведем второй этап минимизации числа внутренних состояний автомата, объединив колонки табл.1, имеющие одинаковые переходы, и отмеченные одинаковыми выходными сигналами. Из табл. 1 следует, что можно объединить состояния 4, 6, 8, 11, 14, 18, 23, 29, 36. Введем новые обозначения внутренних состояний автомата:

0, 1, 2, 3, 4, 5,8,11,14,17,20,23,26,27,29,32,36, 10, 12, 13, 16, 28, 31, 35, 40.

Таблица 2

Проведем еще второй этап минимизации числа внутренних состояний автомата, объединив колонки табл.2, имеющие одинаковые переходы, и отмеченные одинаковыми выходными сигналами. Из табл. 2 следует, что можно объединить состояния ,,,. Введем новые обозначения внутренних состояний автомата: , , ,, ,,,, , , , , , .