Минимизация абстрактного автомата
Автор: Goblin471 • Май 23, 2018 • Практическая работа • 258 Слов (2 Страниц) • 313 Просмотры
ГУАП
КАФЕДРА № 11
ОТЧЕТ
ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
доц., к. т. н., доц. | В. Я. Мамаев | |||
должность, уч. степень, звание | подпись, дата | инициалы, фамилия |
ОТЧЕТ О ПРАКТИЧЕСКОЙ РАБОТЕ |
МИНИМИЗАЦИЯ АБСТРАКТНОГО АВТОМАТА |
по курсу: Алгоритмическое и программное обеспечение |
РАБОТУ ВЫПОЛНИЛ
СТУДЕНТ ГР. № | 1411 | Д.А. Драненков | |||
подпись, дата | инициалы, фамилия |
Санкт-Петербург 2018
1. Цель работы: Задан граф полностью определенного автомата Мура, найти граф автомата с минимальным числом состояний, эквивалентного заданному.
2. Исходные данные:
Таблица.2.1. Исходные данные
w1 | w3 | w2 | w1 | w2 | w1 | |
a0 | a1 | a2 | a3 | a4 | a5 | |
z1 | a4 | a4 | a4 | a0 | a2 | a2 |
z2 | a3 | a5 | a3 | a1 | a3 | a3 |
[pic 1]
Рис. 2.1. Граф исходного автомата.
3. Минимизация:
Найдём разбиение на классы 0-эквивалентных состояний, для этого отыщем состояния с одинаковым выходным сигналом:
.[pic 2]
Учитывая разбиение, составим новую таблицу:
Таблица.3.1.
A1 | A2 | A3 | ||||
a0 | a3 | a5 | a2 | a4 | a1 | |
z1 | A2 | A1 | A3 | A2 | A2 | A2 |
z2 | A1 | A3 | A2 | A1 | A1 | A1 |
Теперь найдем разбиение на классы 1-эквивалентных состояний, то есть при которых автомат, находясь в различных текущих состояниях, при подаче одинаковых входных сигналов переходит в одинаковые состояния:
...