Курсовая работа: Абстрактный синтез конечного автомата

По графу переходов построим таблицу переходов-выходов заданного автомата (таблица 3).

Таблица 3. Таблица переходов-выходов автомата

a(t-1)	0	1
a0	a1 /1	a2 /1
a1	a3 /1	a4 /1
a2	a10 /0	a11 /0
a3	-	a5 /1
a4	-	a6 /1
a5	a8 /1	a9 /0
a6	a8 /0	-
a7	a0 /-	a0 /-
a8	a0 /-	a0 /-
a9	a0 /-	a0 /-
a10	-	a12 /1
a11	a14 /0	a15 /0
a12	a13 /1	-
a13	a0 /-	a0 /-
a14	-	a16 /0
a15	a17 /1	a18 /0
a16	a0 /-	a0 /-
a17	a0 /-	a0 /-
a18	a0 /-	a0 /-

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

0 класс эквивалентности:

a0, a1	b0
a2, a11	b1
a14	b2
a3, a4, a10	b3
a5, a15	b4
a6	b5
a7, a8, a9, a13, a16, a17, a18	b6
a12	b7

1 класс эквивалентности:

a0	c0
a1	c1
a2	c2
a3	c3
a4	c4
a5, a15	c5
a6	c6
a10	c7
a11	c8
a12	c9
a14	c10
a7, a8, a9, a13, a16, a17, a18	c11

2 класс эквивалентности:

a0	d0
a1	d1
a2	d2
a3	d3
a4	d4
a5, a15	d5
a6	d6
a10	d7
a11	d8
a12	d9
a14	d10
a7, a8, a9, a13, a16, a17, a18	d11

Из разбиения видно, что классы 1 и 2 совпадают, значит, продолжать не имеет смысла.

Таблица переходов-выходов минимизированного автомата представлена в таблице 4:

Таблица 4. Таблица переходов-выходов минимизированного автомата

d(t-1)	0	1
d0	d1 /1	d2 /1
d1	d3 /1	d4 /1
d2	d7 /0	d8 /0
d3	-	d5 /1
d4	-	d6 /1
d5	d11 /1	d11 /0
d6	d11 /0	-
d7	-	d9 /1
d8	d10 /0	d5 /0
d9	d11 /1	-
d10	-	d11 /0
d11	d0 /-	d0 /-

Граф переходов минимизированного автомата представлен в приложении 2.

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

2.1 Кодирование состояний, входных и выходных сигналов

Для кодирования состояний, входных и выходных сигналов конечного автомата, необходимо вычислить число элементов памяти:

а) рассчитаем число элементов памяти: Н = ] log₂ h [, где h - число состояний после минимизации D = {}

H = ] log₂ 12 [ = 4

б) рассчитаем число входных (L) и выходных (М) шин:
L = ] log₂ n[

М =] log₂ m [,

где n, m - число букв входного и выходного алфавитов

Z = {0, 1} L = ] log₂ 2 [ = 1

W = {0, 1} M = ] log₂ 2 [ = 1

Из приведённого выше следует, что для кодирования состояний необходимо 4 элемента памяти, обозначим их Q ₀ , …, Q ₃ . Закодируем состояния (таблица 5) случайными кодами.

Таблица 5. Таблица кодированных состояний

d(t-1)	Q0	Q1	Q2	Q3
d0	0	0	0	0
d1	0	0	0	1
d2	0	0	1	0
d3	0	0	1	1
d4	0	1	0	0
d5	0	1	0	1
d6	0	1	1	0
d7	0	1	1	1
d8	1	0	0	0
d9	1	0	0	1
d10	1	0	1	0
d11	1	0	1	1

2.2 Формирование функций возбуждения и выходных сигналов структурного автомата

По минимизированному графу переходов абстрактного автомата (Приложение 2) можно составить таблицу переходов, выходных сигналов и сигналов возбуждения D -триггеров автомата Мили (таблица 6), Т -триггеров автомата Мили (таблица 7), RS -триггеров (таблица 8), JK -триггеров (таблица 9).

D -триггер – элемент задержки – имеет один информационный вход D и один выход Q и осуществляет задержку поступившего на его вход сигнала на один такт. Состояние, в которое переходит триггер, совпадает с поступившим на его вход сигналом D(t).

Таблица 6. Таблица переходов, выходных сигналов и сигналов возбуждения D -триггеров

Номер перехода	Исходное состояние	Код исходного состояния	Следующее состояние	Код следующего состояния	Входной набор	Выходные сигналы		Сигналы возбуждения
						0	1	D3	D2	D1	D0
1	d0	0000	d1 d2	0001 « 1 2 3 4 5 6 7 8 9 » К-во Просмотров: 766 Бесплатно скачать Курсовая работа: Абстрактный синтез конечного автомата >>> Скачать <<< Меню Поиск