- •Введение
- •1. Функциональные модели дискретных устройств
- •1.1. Автоматы
- •1.2. Классификация автоматов
- •1.3. Способы задания конечных автоматов
- •1.4. Система формул переходов
- •1.5. Граф-схема алгоритма
- •1.7.1. Переход от гса к автомату Мура
- •1.6. Переход от сфп к гса
- •1.7. Переход от гса к автомату
- •1.7.2. Переход от гса к автомату Мили
- •1.8. Задачи
- •2. Минимизация автоматов
- •2.1. Минимизация полных автоматов
- •2.1.1. Неотличимость состояний
- •Алгоритм поиска неотличимых состояний автомата
- •2.1.2. Приведенная форма автомата
- •2.1.3. Построение классов неотличимости: алгоритм Мура
- •Свойства разбиения
- •Алгоритм Мура построения классов неотличимости
- •2.1.4. Построение классов неотличимости: алгоритм Хопкрофта
- •Алгоритм Хопкрофта
- •2.2. Минимизация частичных автоматов
- •2.2.1. Совместимость состояний
- •Алгоритм построения множеств совместимости
- •2.2.2. Сохраняемое правильное покрытие
- •Алгоритм построения кратчайшего сохраняемого правильного покрытия
- •2.2.3. Метод последовательных сокращений
- •Алгоритм последовательных сокращений
- •2.3. Задачи
2.3. Задачи
Задача 1. Минимизировать полный автомат с помощью графа условий неотличимости, алгоритмов Мура и Хопкрофта.
a) |
|
|
|
|
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a |
8 |
8 |
8 |
1 |
2 |
3 |
3 |
3 |
b |
2 |
2 |
6 |
5 |
4 |
8 |
1 |
4 |
c |
2 |
1 |
8 |
3 |
3 |
8 |
8 |
1 |
d |
5 |
4 |
7 |
6 |
7 |
5 |
5 |
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
b |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
c |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
d |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
b) |
|
|
|
|
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a |
3 |
4 |
5 |
5 |
4 |
3 |
4 |
3 |
b |
5 |
5 |
2 |
1 |
2 |
7 |
6 |
8 |
c |
6 |
8 |
7 |
8 |
3 |
1 |
2 |
1 |
d |
8 |
7 |
1 |
1 |
6 |
6 |
8 |
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
b |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
c |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
d |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
Задача 2. Минимизировать частичный автомат точным методом и методом последовательных сокращений, сравнить результаты.
a) |
|
|
|
|
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a |
4 |
– |
2 |
6 |
3 |
2 |
– |
7 |
b |
– |
– |
– |
– |
4 |
3 |
5 |
– |
c |
5 |
5 |
– |
– |
– |
– |
5 |
5 |
d |
7 |
– |
8 |
– |
– |
– |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a |
1 |
– |
1 |
0 |
1 |
0 |
– |
1 |
b |
– |
– |
– |
– |
1 |
1 |
0 |
– |
c |
1 |
1 |
– |
– |
– |
– |
0 |
0 |
d |
0 |
– |
0 |
– |
– |
– |
1 |
1 |
|
|
|
|
|
|
|
|
|
b) |
|
|
|
|
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a |
5 |
8 |
8 |
4 |
7 |
7 |
5 |
5 |
b |
2 |
1 |
– |
– |
8 |
– |
– |
7 |
c |
3 |
– |
– |
5 |
7 |
4 |
– |
2 |
d |
3 |
6 |
1 |
2 |
– |
– |
– |
– |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X\Q |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
a |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
b |
1 |
1 |
– |
– |
1 |
– |
– |
1 |
c |
1 |
– |
– |
1 |
0 |
0 |
– |
0 |
d |
0 |
0 |
0 |
1 |
– |
– |
– |
– |
Задача 3. Минимизировать автоматы из задач раздела 1.8.