курсовая работа по теории автоматов. курс ТА. Теория автоматов

• Название: Теория автоматов
• Анкор: курсовая работа по теории автоматов
• Дата: 12.09.2022
• Размер: 0.88 Mb.
• Имя файла: курс ТА.docx
• Тип: Пояснительная записка; #673878
• страница: 5 из 6

5
Рис. 6. Граф-схема автомата Мура, выполняющего операции деления
.3. Определение числа элементов памяти и кодирование состояний автомата

Число элементов памяти N автомата Мили определяем по выражению

N , М – число состояний автомата. Отсюда N = = 4.

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

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

1. 
   По графу или таблице переходов автомата составляем матрицу Т, строки которой образуют пары состояний, между которыми возможен переход. Каждой паре состояний автомата ставится в соответствие вес перехода, определяемый в соответствии с выражением
   

P(i,j) = q(i,j) + q(j,i),

где q(i,j) – количество дуг, идущих от i-го состояния к j-му на графе состояний автомата;

q(j,i) – количество дуг, идущих от j-го состояния к i-му на графе состояний автомата.

Критерием сложности синтезированной комбинационной схемы автомата является величина

W = ,

где d(i,j) – кодовое состояние по Хеммингу, то есть количество символов, которыми отличаются коды состояний iиj. Чем меньше W, тем проще схема.

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

При упорядочивании матрицы необходимо также учитывать правило, при котором в каждой последующей паре содержится одна компонента (состояние) из предыдущей пары, даже если эта пара имеет меньший вес P(i,j) или меньший суммарный вес. То есть это правило имеет приоритет перед другими.

	Пары состояний, образующих матрицу Т				Вес перехода P(i, j)				Суммарный вес перехода						Упорядоченная матрица М
	1	2				1				14						9	1
	1	3				1				14						1	2
	1	5				1				13						1	3
	1	7				1				12						1	5
	1	8				1				12						12	1
	2	9				1				10						1	7
	3	4				2				7						1	8
	5	6				2				7						10	1
T=	6	2				1				8				M=		9	11
	6	3				1				8						6	2
	7	9				1				8						3	4
	8	9				1				8						2	9
	9	1				1				16						6	3
	9	10				1				8						7	9
	9	11				1				9						8	9
	10	1				1				12						9	10
	11	12				2				6						5	6
	12	1				1				13						11	12

3. 
   Состояния первой строки матрицы М кодируем начальными кодовыми комбинациями
   

к( ) = 0000, к( ) = 0001.

4. 
   Для незакодированного состояния второй строки а₂ составляем дополнительную матрицу , где ɣ обозначено незакодированное состояние второй строки, равное его номеру. В матрицу введём все строчки, содержащие ɣ.
   

. Множество уже закодированных состояний, содержащихся в матрице M₆, равно .

4. 
   Составляем множество кодовых комбинаций для состояния (a₆) с учётом условий соседнего кодирования. Для подбора кодов можно использовать карту Карно. Составим карту Карно для трёх переменных и запишем закодированные состояния a₉ и a₁ в соответствии с их кодами в клетки карты Карно.
   

х₁ х₂

х3x4	00	01	11	10
00	а9	*		*
01	а1	*		*
11	*
10	*

Так как в переходе а₆ – а₂ состояние а₆ не закодировано, то для нахождения кода для состояния а₂ используется только переходы а₁ – а₂ и а₂ – а₉. Отметим звёздочками соседние к уже закодированным состояниям а₉и а₁ клетки карты Карно, получим: для к(а₉) = 0000 и к(а₉) = 0001 – множество соседних клеток (кодов)

Для каждой кодовой комбинации из вычисляем .
Таблица 3

Расчёт функции W при выборе кода для состояния

Соседние коды по карте Карно (множество )	Состояние и код				Функция W W = ∑P(i,j)*d(i,j)
	= 0000		= 0001
	Вес перехода из в	Кодовое расстояние d(9,2)	Вес перехода из в	Кодовое расстояние d(1,2)
0100	1	1	1	2	3
0101	1	2	1	1	3
0011	1	2	1	1	3
1000	1	1	1	2	3
1001	1	2	1	1	3

Функция Wимеет одинаковое значение для всех кодов, поэтому можно выбрать любой, возьмём по порядку написания код 0100, то есть к(а₂) = 0100.

Повторяем пункты 4,5 для того, чтобы закодировать все незакодированные состояния автомата.

Для третьей строки в переходе а₁ – а₃ не закодировано состояние а₃.

. Множество уже закодированных состояний, содержащихся в матрице М₃, равно В₃ = {1}.

х3x4	00	01	11	10
00	а9	а2
01	а1	*		*
11	*
10

х₁ х₂




Таблица 4

Расчёт функции W при выборе кода для состояния

Соседние коды по карте Карно (множество )	Состояние и код		Функция W W = ∑P(i,j)*d(i,j)
	= 0001
	Вес перехода из в	Кодовое расстояние d(1,3)
0101	1	1		1
0011	1	1		1
1001	1	1		1

Возьмём по порядку написания код 0101, то есть к(а₃) =0101.

Для четвёртой строки в переходе а₁ – а₅ не закодировано состояние а₅.

. Множество уже закодированных состояний, содержащихся в матрице M₅, равно B₅ = {1}.


х₁ х₂

х3x4	00	01	11	10
00	а9	а2
01	а1	а3		*
11	*
10

Таблица 5

Расчёт функции W при выборе кода для состояния

Соседние коды по карте Карно (множество )	Состояние и код		Функция W W = ∑P(i,j)*d(i,j)
	= 0001
	Вес перехода из в	Кодовое расстояние d(1,5)
0011	1	1		1
1001	1	1		1

Возьмём по порядку написания код 0101, то есть к(а₅) =0011.

Для пятой строки в переходе не закодировано состояние а₁₂.

. Множество уже закодированных состояний, содержащихся в матрице M₁, равно B₁ = {1}.

х3x4	00	01	11	10
00	а9	а2
01	а1	а3		*
11	а5
10

х₁ х₂




Получим код к(а₁₂) = 1001.

Для шестой строки в переходе а₆ – а₂ не закодировано состояние а₆.

. Множество уже закодированных состояний, содержащихся в матрице M₇, равно В₇ = {2, 3, 5}.


х₁ х₂

х3x4	00	01	11	10
00	а9	а2	*
01	а1	а3	*	а12
11	а5	*		*
10	*

Таблица 6

Расчёт функции W при выборе кода для состояния

Соседние коды по карте Карно (множество )	Состояние и код				Функция W W = ∑P(i,j)*d(i,j)
	= 0100		= 0101
	Вес перехода из в	Кодовое расстояние d(2,6)	Вес перехода из в	Кодовое расстояние d(3,6)
1100	1	1	1	2		3
1101	1	2	1	1		3
0111	1	2	1	1		3
1011	1	4	1	3		7
0010	1	2	1	3		5

Возьмём по порядку написания код 1100, то есть к(а₆) =1100.

Для седьмой строки в переходе а₉ – а₁₁ не закодировано состояние а₁₁.

. Множество уже закодированных состояний, содержащихся в матрице M₁₁, равно В₁₁ = {9,12}.

х3x4	00	01	11	10
00	а9	а2	а6	*
01	а1	а3	*	а12
11	а5			*
10	*

х₁ х₂




Таблица 7

Расчёт функции W при выборе кода для состояния

Соседние коды по карте Карно (множество )	Состояние и код		Состояние и код			Функция W W = ∑P(i,j)*d(i,j)
	= 011		= 100
	Вес перехода из в	Кодовое расстояние d(6,7)		Вес перехода из в	Кодовое расстояние d(1,7)
1000	1	1		2	1		3
1101	1	3		2	1		5
1011	1	3		2	1		5
0010	1	1		2	3		7

Возьмём код к(а₁₁) = 1000.
Для восьмой строки в переходе а₇ – а₉ не закодировано состояние а₁₁.

. Множество уже закодированных состояний, содержащихся в матрице M₁₁, равно В₁₁ = {9,12}.

х3x4	00	01	11	10
00	а9	а2	а6	а11
01	а1	а3		а12
11	а5
10	*

Получается код к(а₇) = 0010.

А
х₁ х₂

налогично для остальных состояний получаем к(а₄) = 1011, к(а₈) = 1111,

к(а₁₀) = 1110.

Таким образом, состояния автомата получили следующие коды: к(а₁) = 0001, к(а₂) = 0100, к(а₃) = 0101, к(а₄) = 1011, к(а₅) = 0011, к(а₆) = 1100, к(а₇) = 0010,

к(а₈) = 1111, к(а₉) = 0000, к(а₁₀) = 1110, к(а₁₁) = 1000, к(а₁₂) = 1001.