Дискретная математика. ДМ. Министерство образования республики беларусь

• Название: Министерство образования республики беларусь
• Анкор: Дискретная математика
• Дата: 02.05.2021
• Размер: 107.85 Kb.
• Имя файла: ДМ.docx
• Тип: Задача; #200853
• страница: 3 из 5

Закодируем заданный автомат методом «желательных соседств»

По виду представленной таблицы можно определить, что задан автомат Мили.
Таблица переходов

	00	01	10	11
1	-	0	-	0
2	1	0	-	0
3	0	-	-	1
4	1	-	1	1

Таблица выходов.

	00	01	10	11
1	-	3	-	4
2	1	4	-	3
3	3	-	2	1
4	2	3	4	1

Определим длину входного алфавита:



Определим длину выходного алфавита:



Определим количество элементов памяти (JS-триггеров), которые будут кодировать внутренние состояния МПА:






Рис. 1. Структурная схема автомата


На основании имеющихся и выше полученных данных заполним прямую структурную таблицу автомата Мили (таблица Мили).

Прямая структурная таблица Мили

№ п/п	Исходное состояние	Код исход. состояния	Состояние перехода	Код сост. перехода	Входной сигнал	Выходной сигнал	Функция возбуждения
	am	K(am)	as	K(as)	X(am,as)	Y(am,as)	F(am,as)
		t1 t2		t1 t2	х1х2	y1y2	J1K1J2K2
1	а1	00	-	-	z1	-
2	-	-	а1	00	z1	w3
3	а1	00	-	-	z1	-
4	а1	00	а2	01	z2	w1
5	а2	01	а1	00	z2	w4
6	а1	00	-	-	z2	-
7	а1	00	а1	00	z3	w3
8	а1	00	-	-	z3	-
9	-	-	-	-	z3	w2
10	а1	00	а2	01	z4	w2
11	а2	01	-	-	z4	w3
12	-	-	а2	01	z4	w4

Отсортируем таблицу по исходному состоянию и состоянию перехода, а столбец «функция возбуждения» заполним так, чтобы любые два соседние состояния автомата отличались бы лишь одним изменением состояния элемента памяти. В результате получим:

Прямая структурная таблица Мили

№ п/п	Исходное состояние	Код исход. состояния	Состояние перехода	Код сост. перехода	Входной сигнал	Выходной сигнал	Функция возбуждения
	am	K(am)	as	K(as)	X(am,as)	Y(am,as)	F(am,as)
		t1 t2		t1 t2	х1х2	y1y2	J1K1J2K2
1	а1	00	-	-	z1	-
2	а1	00	-	-	z1	-
3	а1	00	-	-	z2	-
4	а1	00	-	-	z3	-
5	а1	00	а1	00	z3	w3
6	а1	00	а2	01	z2	w1
7	а1	00	а2	01	z4	w2
8	а2	01	-	-	z4	w3
9	а2	01	а1	00	z2	w4
10	-	-	-	-	z3	w2
11	-	-	а1	00	z1	w3
12	-	-	а2	01	z4	w4