Минимизация полностью определенных автоматов
Минимизация автоматов Мили
Рассматривается метод p-разбиения.
Идея алгоритма.
1. В таблице переходов/выходов выделяются группы столбцов, имеющие одинаковую выходную реакцию (в нижеследующем примере столбцы групп помечены *,+). Состояния, соответствующие одинаково помеченным столбцам составляют один класс эквивалентности. Полученные классы эквивалентности составляют начальное разбиение p1.
2. Для дальнейших попыток разбиения исходная талица переписывается. Состояния группируются по принадлежности к классу эквивалентности. Содержимым ячеек теперь являются найденные классы эквивалентности, соответствующие находившимся там состояниям. Для этого анализируется исходная таблица. Например в столбце для состояния 1 будет записано: А2 А1 , т.к. 3 состояние попало в класс А2 , а 5 состояние – в класс А1.
3. В полученной таблице опять производится попытка выделить эквивалентные классы. Ссостав новых классов также определяется сравнением содержимого столбцов в пределах одного класса. Найденные новые классы эквивалентности составляют разбиение p2 .
4. Проводится сравнение разбиений p1 и p2, если они одинаковы, т.е. одинаков состав классов эквалентности, то разбиение считается завершенным, в противном случае попытки построения нового разбиения продолжаются.
5. Если разбиение закончено, производится построение минимизированной таблицы автомата. Из каждого класса последнего разбиения Ci выбирается по одному состоянию и они переобозначаются в терминах Si . Эти состояния будут составлять новый автомат, столбец входных букв переписывается, добавляются столбцы состояний, по количеству полученных состояний Si . Ячейки новой таблицы заполняются следующим образом: берется очередное состояние Si , определяется, какие состояния исходной талицы ему эквивалентны и в новую таблицу записываются выходные реакции, содержащиеся в соответствующих столбцах исходной таблицы, для записи состояний анализируется, какому классу эквивалентности принадлежит состояние, записанное в соответствующей ячейке исходной таблицы, а затем, какое новое состояние соответствует этому же классу эквивалентности и оно записывается в новую таблицу в соответствующую ячейку.
|
|
|
Пример 1. Задан автомат Мили совмещенной таблицей переходов/выходов. Минимизировать данный автомат.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| z 1 | 3 Y1 | 4 Y1 | 3 Y1 | 4 Y1 | 1 Y1 | 2 Y1 |
| z 2 | 5 Y1 | 6 Y1 | 5 Y2 | 6 Y2 | 3 Y1 | 4 Y1 |
| * | * | + | + | * | * |
Решение.
1. Определить эквивалентные состояния. На вход автомата подается слова длины 1: |p|=1.
1 класс А1={1, 2, 5, 6}
2 класс А2={3, 4}
|
|
|
p1={A1, A2}
2. Классы Аi подвергаются анализу на предмет их расщепления при подаче слов длины 2: |p|=2.
| А1 | А 2 | |||||
| 1 | 2 | 5 | 6 | 3 | 4 | |
| z 1 | А 2 | А 2 | А1 | А1 | А 2 | А 2 |
| z 2 | А1 | А1 | А 2 | А 2 | А1 | А1 |
| B 1 | B2 | B3 | ||||
1 класс B1={1, 2 }
2 класс B2={5, 6}
3 класс B3={3, 4}
p2={B1, B2, B3}, p1 ¹ p2 , следовательно расщепление еще не закончено.
3. Классы Bi подвергаются анализу на предмет их расщепления при подаче слов длины 3: |p|=3.
| B 1 | B2 | B3 | ||||
| 1 | 2 | 5 | 6 | 3 | 4 | |
| z 1 | B3 | B3 | B 1 | B 1 | B3 | B3 |
| z 2 | B2 | B2 | B3 | B3 | B2 | B2 |
| C 1 | C2 | C3 | ||||
1 класс C1={1, 2 }
2 класс C2={5, 6}
3 класс C3={3, 4}
p3={C1, C2, C3}, p2 = p3 , следовательно расщепление закончено.
4. Из каждого класса Ci выбирается по одному состоянию и они переобозначаются в терминах Si .
1 класс C1={1, 2 } 1 S 0
2 класс C2={5, 6} 5 S 1
3 класс C3={3, 4} 4 S 2
| S 0 | S 1 | S 2 | |
| z 1 | S2 Y1 | S0 Y1 | S2 Y1 |
| z 2 | S1 Y1 | S2 Y1 | S1 Y2 |
В качестве проверки правильности минимизации на вход подается комбинация X1X2X2X1
Выходные реакции в исходном и минимизированном автоматах совпадают.
Минимизация автоматов Мура
При минимизации автоматов Мура вводится понятие 0-эквивалентности состояний и разбиения множества состояний на 0-классы.
|
|
|
0-эквивалентными называются любые одинаково отмеченные состояния автомата Мура.
Если два 0-эквивалентных состояния любым входным сигналом переводятся в два 0—эквивалентных состояния, то они называются 1-эквивалентными.
Все дальнейшие классы эквивалентностей состояний для автомата Мура определяются аналогично, как и для автомата Мили.
Пример 2. Задан автомат Мура отмеченной таблицей переходов. Минимизировать данный автомат.
| Y1 | Y 2 | Y3 | Y 1 | Y 2 | Y2 | Y3 | |
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | |
| 1 | a5 | a4 | a5 | a3 | a4 | a2 | a5 |
| 2 | a7 | a1 | a4 | a2 | a1 | a3 | a4 |
| * | + | * | + | + |
Решение.
Классы 0-эквивалентности
| B1 | B2 | B3 | |||||
| a1 | a 4 | a 2 | a 5 | a 6 | a 3 | a 7 | |
| 1 | B2 | B3 | B1 | B1 | B2 | B2 | B2 |
| 2 | B3 | B2 | B1 | B1 | B3 | B1 | B1 |
| C1 | C2 | C3 | C4 | C5 | |||
B1 ={a1, a4}
B2 ={a2, a5, a6}
B3 ={a3, a7}
P0 = {B1, B2, B3}
Дальнейшее разбиение на Классы эквивалентности
| C1 | C2 | C3 | C4 | C5 | |||
| a1 | a 4 | a 2 | a 5 | a 6 | a 3 | a 7 | |
| 1 | C3 | C5 | C2 | C2 | C3 | C3 | C3 |
| 2 | C5 | C3 | C1 | C1 | C5 | C2 | C2 |
| D1 | D2 | D3 | D4 | D5 | |||
C1 = { a1}
C2 = { a4}
C3 = { a2, a5}
C4 = { a6}
C5 = { a3, a7}
P1={ C1, C2 ,C3 ,C4 ,C5}
| D1 | D2 | D3 | D4 | D5 | |||
| a1 | a 4 | a 2 | a 5 | a 6 | a 3 | a 7 | |
| 1 | D3 | D5 | D2 | D2 | D3 | D3 | D3 |
| 2 | D5 | D3 | D1 | D1 | D5 | D2 | D2 |
D1 = { a1} a1 S1
|
|
|
D2 = { a4} a4 S2
D3 = { a2, a5} a5 S3
D4 = { a6} a6 S4
D5 = { a3, a7} a3 S5
P2={ D1, D2 ,D3 ,D4 ,D5}
P1= P2, разбиение закончено.
Результирующая таблица минимизированного автомата Мура
| y1 | y1 | y2 | y2 | y3 | |
| S1 | S2 | S3 | S4 | S5 | |
| 1 | S3 | S5 | S2 | S3 | S3 |
| 2 | S5 | S3 | S1 | S5 | S2 |
Задание к работе:
| 1. Задан автомат A7 Мура в виде графа. Построить отмеченную таблицу переходов. Найти эквивалентный ему автомат Мили, построить граф и совмещенную таблицу переходов/выходов. | |
2. Задан автомат A8 Мили в виде графа. Построить совмещенную таблицу переходов/выходов. Найти эквивалентный ему автомат Мура, построить граф и отмеченную таблицу переходов.
3. Интуитивно построить автомат Мура, на выходе которого возникает реакция С, если сумма поступивших разрядов равна 1, перенос не учитывать, если сумма равна 0, то возникает реакция Z. Автомат многоразовый, т.е. должен быть возврат в исходное состояние.
4. Минимизировать автомат, заданный таблицей.
| S1 | S2 | S 3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 | S11 | S12 | |
| z 1 | S10 Y1 | S12 Y1 | S5 Y2 | S7 Y2 | S3 Y1 | S7 Y2 | S3 Y1 | S10 Y1 | S7 Y2 | S1 Y2 | S5 Y2 | S2 Y2 |
| z 2 | S5 Y2 | S8 Y2 | S6 Y1 | S11 Y1 | S9 Y2 | S11 Y1 | S6 Y2 | S4 Y2 | S6 Y1 | S8 Y1 | S9 Y1 | S8 Y1 |
5. Минимизировать автомат, заданный графом.
6. Минимизировать автомат, заданный таблицей.
| Y1 | Y 1 | Y3 | Y3 | Y3 | Y2 | Y3 | Y 1 | Y2 | Y2 | Y 2 | Y2 | |
| q1 | q2 | q3 | q4 | q 5 | q 6 | q 7 | q 8 | q 9 | q 10 | q 11 | q 12 | |
| X 1 | q10 | q12 | q5 | q7 | q3 | q7 | q3 | q10 | q7 | q1 | q5 | q2 |
| X 2 | q5 | q7 | q6 | q11 | q9 | q11 | q6 | q4 | q6 | q8 | q9 | q8 |
Порядок выполнения работы:
1. Изучить инструкцию к практической работе.
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1. Перечислите способы задания конечного автомата?
2. Как понять алфавит автомата?
3. Что такое класс эквивалентности?
Практическая работа № 20
Тема: Синтез автоматов по дереву управления
Цель: изучить синтез автоматов по дереву управления.
Задачи: использования специального программного обеспечения для моделирования; построение адекватной модели.
Материальное обеспечение: практическая работа, программное обеспечение
Дата добавления: 2019-02-22; просмотров: 3081; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!