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

Цель: освоение навыка построения минимального и приведенного конечного автомата.

Задание 1.

Найдите недостижимые состояния автомата

	0	1	2
A	C	E	G	0
B	J	E	G	1
C	J	A	H	0
D	F	A	G	1
E	E	J	H	0
F	D	I	A	1
G	H	A	J	0
H	G	J	B	1
I	D	F	G	0
J	B	H	G	1

Рекомендуемая литература: [2], [3], конспект лекций.

Этапы выполнения.

1. Построить множество достижимых состояний данного автомата, начиная с начального состояния.

2. Сформировать множество недостижимых состояний из состояний, непопавших в первое множество.

3. Удалить недостижимые состояния из таблицы переходом заданного автомата.

4. Построить результирующую таблицу переходов.

Задание 2.

Найдите минимальную эквивалентную таблицу переходов для каждого из следующих автоматов:

	0	1
1	1	3	0
2	7	4	1
3	6	5	0
4	1	4	1
5	1	4	0
6	7	6	1
7	7	3	0

	X	Y
1	4	1	1
2	5	1	1
3	4	5	0
4	2	6	0
5	1	7	0
6	1	4	1
7	2	5	1

Рекомендуемая литература: [2], [3], конспект лекций.

Этапы выполнения.

Для каждого автомата:

1. Построить таблицу для поиска эквивалентных состояний для каждой пары подобных состояний.

2. Сделать вывод об эквивалентности исследуемой пары и всех других пар, вошедших в таблицу эквивалентности.

3. Используя свойства отношения эквивалентности, сделать вывод об эквивалентности состояний, входящих в разные пары эквивалентных состояний.

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

5. Построить результирующую таблицу переходов.