Задание 15. Решение Нахождение всех максимальных независимых множеств будем осуществлять последовательным перебором независимых множеств с одновременной проверкой каждого множества на максимальность (путем добавления к исследуемому множеству дополнительной,

• Название: Решение Нахождение всех максимальных независимых множеств будем осуществлять последовательным перебором независимых множеств с одновременной проверкой каждого множества на максимальность (путем добавления к исследуемому множеству дополнительной,
• Дата: 08.06.2022
• Размер: 334.5 Kb.
• Имя файла: Задание 15.doc
• Тип: Решение; #577425
• страница: 2 из 3

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



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



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

.

На рисунке представлена структурная схема автомата:



Заполним прямую структурную таблицу автомата Мили:

№ п/п	Исходное состояние	Код исход. состояния	Состояние перехода	Код сост. перехода	Входной сигнал	Выходной сигнал	Функция возбуждения
	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	a2	01	а1	00	z1	w3
3	а1	00	а1	00	z1	w5
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	а2	01	-	-	z3	-
9	а1	00	-	-	z3	w2
10	а1	00	а2	01	z4	w2
11	а2	01	-	-	z4	w3
12	а1	00	а2	01	z4	w4
13	а1	00	a1	00	z5	w4
14	а2	01	a2	01	z5	w2
15	а1	00	a2	01	z5	w3

Отсортируем полученную таблицу по исходному состоянию и состоянию перехода. Получим следующую таблицу:

№ п/п	Исходное состояние	Код исход. состояния	Состояние перехода	Код сост. перехода	Входной сигнал	Выходной сигнал	Функция возбуждения
	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	-	-	z2	-
3	а1	00	-	-	z3	w2
4	а1	00	а1	00	z1	w5
5	а1	00	а1	00	z3	w3
6	а1	00	a1	00	z5	w4
7	а1	00	а2	01	z2	w1
8	а1	00	а2	01	z4	w2
9	а1	00	а2	01	z4	w4
10	а1	00	a2	01	z5	w3
11	а2	01	-	-	z3	-
12	а2	01	-	-	z4	w3
13	a2	01	а1	00	z1	w3
14	а2	01	а1	00	z2	w4
15	а2	01	a2	01	z5	w2

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

Так же учитываем, что при соседнем кодировании в графе автомата не должно быть циклов с нечётным числом, но так как у нас возможны только 3 состояния перехода а1, а2, а3, то при кодировании нужно использовать только два состояния. Доопределим неопределенные элементы автомата. Но будем учитывать, что доопределять можно только переходами а₁–а₁, а₁–а₂, а₂–а₁, а₂–а₂. После доопределения получим таблицу:

№ п/п	Исходное состояние	Код исход. состояния	Состояние перехода	Код сост. перехода	Входной сигнал	Выходной сигнал	Функция возбуждения
	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	а1	00	z1	w2
2	а1	00	a2	01	z2	w3	J2
3	а1	00	а1	00	z3	w2
4	а1	00	а1	00	z1	w5
5	а1	00	а1	00	z3	w3
6	а1	00	a1	00	z5	w4
7	а1	00	а2	01	z2	w1	J2
8	а1	00	а2	01	z4	w2	J2
9	а1	00	а2	01	z4	w4	J2
10	а1	00	a2	01	z5	w3	J2
11	а2	01	а1	00	z3	w4	K2
12	а2	01	a2	01	z4	w3
13	a2	01	а1	00	z1	w3	K2
14	а2	01	а1	00	z2	w4	K2
15	а2	01	a2	01	z5	w2