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

АЛГОРИТМ РАБОТЫ АВТОМАТА …………………………………..3

ГЛАВА 1. АБСТРАКТНЫЙ СИНТЕЗ АВТОМАТА ………………...4

1.1. Составление регулярных выражений..............................................................4
1.2. Разметка мест регулярных выражений ..........................................................5
1.3. Первый этап минимизации .............................................................................6
1.4. Составление отмеченной таблицы переходов ...............................................7
1.5. Второй этап минимизации ..............................................................................7

ГЛАВА 2. СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА..........................10

2.1 Определение параметров схемы ...................................................................10
2.2 Кодирование состояний ................................................................................10
2.3 Построение кодированной таблицы переходов ..........................................11
2.4 Составление диаграмм Вейча .......................................................................13
2.5 Определение типов используемых триггеров .............................................16
2.6 Построение схемы .........................................................................................17

СПИСОК ЛИТЕРАТУРЫ .......................................................................18

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

Сигнал у1 выдается после трехбуквенных слов, содержащих не менее двух букв х2 и продолжает выдаваться после каждой следующей буквы до тех пор, пока на вход автомата не поступает подряд 5 букв х1, после поступления которых выдается сигнал у2. Если в дальнейшем на вход автомата поступит буква х2, то выдается сигнал у3.
Синтез автомата провести на D-триггерах и логических элементах И, ИЛИ, НЕ. Коэффициент объединения по входу равен четырем, коэффициент разветвления по выходу – четырем.

Курсовая работа по дисциплине – «Теория автоматов»3

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

Сигнал у1 выдается после трехбуквенных слов, содержащих не менее двух букв х2 и продолжает выдаваться после каждой следующей буквы до тех пор, пока на вход автомата не поступает подряд 5 букв х1, после поступления которых выдается сигнал у2. Если в дальнейшем на вход автомата поступит буква х2, то выдается сигнал у3.
Синтез автомата провести на D-триггерах и логических элементах И, ИЛИ, НЕ. Коэффициент объединения по входу равен четырем, коэффициент разветвления по выходу – четырем.

Курсовая работа по дисциплине – «Теория автоматов»4

Глава 1. Абстрактный синтез автомата
Синтез конечного автомата проводят в два этапа.
...

1.1. Составление регулярных выражений
Составим регулярные выражения S₁, S₂ и включающие все слова, при поступлении которых автомат выдает буквы у₁, у₂, y3 и е.
Событие, включающее все трехбуквенные слова алфавита Х, содержащих не менее двух букв х2, записывается в виде выражения:
(x2x2x2 v x2x2x1 v x2x1x2 v x1x2x2 ). Умножая это событие на событие {x2 v x1x2 v x1x1x2 v x1x1x1x2 v x1x1x1x1x2}, которое включает все слова, оканчивающиеся на х2, и не имеющие серии из пяти подряд идущих букв х1, получим событие S:
S= (x2x2x2 v x2x2x1 v x2x1x2 v x1x2x2 ) {x2 v x1x2 v x1x1x2 v x1x1x1x2 v x1x1x1x1x2}
Учитывая, что событие S₁, представленное в автомате буквой у₁, получим следующее выражение для S₁:
S₁=S v Sx1 v Sx1x1 v Sx1x1x1 v Sx1x1x1x1.
...

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

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

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

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

1.4. Составление отмеченной таблицы переходов
По окончательному размеченному выражению составим отмеченную таблицу переходов автомата. Из размеченного выражения следует, что входной сигнал х₁ переводит автомат из состояния 0 в состояние 1, а сигнал х₂ из этого состояния переводит автомат в состояние 0. Аналогично определяются переходы автомата и из других внутренних состояний. Учитывая, что в состояниях 0, 1, 2, 4, 8, 10, 11 автомат выдает пустую букву е, в состояниях 3, 6, 9, 12,13,14, 15,17,18, 21, 22, 26,27 автомат выдает букву у₁, в состоянии 32 выдает у₂, в состоянии 33 выдает у3 получим следующую отмеченную таблицу переходов автомата (таблица 1):

Таблица 1

yg
е
е
е
у1
у₁
е
у1
е
е
у1
у₁
у₁
у₁
у₁
у₁
у₁
у₁
у₁
у1
у2
у3
a
0
1
2
3
6
8
9
10
11
12
13
14
15
17
18
21
22
26
27
32
33
х₁
10
8
6
14
14
10
14
10
8
14
14
17
14
21
14
26
14
32
14
10
10
х₂
1
2
3
13
13
9
13
11
12
13
13
15
13
18
13
22
13
27
13
33
1

1.5.
...

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

2.3.Построение кодированной таблицы переходов
При синтезе схемы конечного автомата Мура с учетом таб.4-6 построим кодированную таблицу переходов и таблицу кодированных выходов, которые определяют зависимость состояний триггеров (t+l) в момент времени t+1 от состояний триггеров и входных сигналов в предшествующий момент времени t и зависимость выходных сигналов Zn(t) от состояний триггеров в тот же момент времени t.
...

2.4. Составление диаграмм Вейча
Рассматривая столбцы 1-5 и 10-19 таблицы 7 как таблицу истинности десяти булевых функций Z₁(t), Z₂(t), D1(t), D2(t), D3(t), D₄(t), проведем синтез комбинационной части автомата. Для минимизации этих функций воспользуемся диаграммами Вейча для функции Z₁(t), Z₂(t) строится на основе столбцов 2-5, 10-11 таблицы 7 и является диаграммой для четырех переменных. Функции возбуждения триггеров зависят как от состояний автомата, так и от входных сигналов, и поэтому диаграммы Вейча для них составляются на основе столбцов 1-5 и 12-15 таблицы 7. В клетках диаграммы Вейча для них соответствующих запрещенным комбинациям состояний триггеров, проставляются прочерки и являются диаграммами для пяти переменных. В результате имеем десять диаграмм Вейча по числу минимизированных функций, которые приведены на рисунке 1.
...