2014-02-09
2747
1. По таблице выхода находятся состояния с одинаковыми выходными сигналами. Данные состояния объединяются в класс одноэквивалентных состояний. Проводится перекодировка.
2. По таблице перехода определяются классы двухэквивалентных состояний: для любого класса выделяется состояние, которое на одинаковый входной сигнал переходит в одинаковое состояние. Объединяем двухэквивалентные состояния в классы двухэквивалентных состояний. Проводится перекодировка.
3. Алгоритм выполняется, пока в классах k-эквивалентных состояний не находятся одинаковые состояния.
4. Вводятся новые состояния, соответствующие классам эквивалентных состояний.
5. С учетом новых состояний переписываются таблицы перехода и выхода.
ПРИМЕР
Пусть задан автомат Мили
Таблица выходов
| |||||||||
| |||||||||
|
Таблица переходов
|
| |||||||||
|
| |||||||||
|
|
Определяем класс одноэквивалентных состояний по таблице выхода
|
|
|
Таблица выходов
|
| |||||||||
|
| |||||||||
|
| |||||||||
| а | в | а | в | а | в | а | в |
Выделяются два класса одноэквивалентных состояний a ={1,3,5,7,8} и b ={2,4,6,9}. Перегруппируем таблицу перехода по классам одноэквивалентных состояний
Таблица переходов
| а | в | ||||||||
|
| |||||||||
|
| |||||||||
|
|
Перекодируем состояния по полученным классам
Таблица переходов
| а | в | ||||||||
|
| 2/в | 2/в | 6/в | 6/в | 4/в | 1/а | 3/а | 8/а | 7/а |
|
| 2/в | 2/в | 4/в | 2/в | 4/в | 4/в | 2/в | 9/в | 9/в |
|
| 5/а | 5/а | 3/а | 8/а | 7/а | 4/в | 2/в | 6/в | 7/а |
Выделяем внутри каждого из классов одинаковые состояния, тем самым определяя классы двухэквивалентных состояний
Таблица переходов
| а | в | ||||||||
|
| 2/в | 2/в | 6/в | 6/в | 4/в | 1/а | 3/а | 8/а | 7/а |
|
| 2/в | 2/в | 4/в | 2/в | 4/в | 4/в | 2/в | 9/в | 9/в |
|
| 5/а | 5/а | 3/а | 8/а | 7/а | 4/в | 2/в | 6/в | 7/а |
| а | в | с |
Определим новые классы двухэквивалентных состояний a ={1,3,5,7,8}, b ={2,4,6}, c ={9}, перекодируем по новым состояниям и выделим классы трехэквивалентных состояний
Таблица переходов
| а | в | с | |||||||
|
| 2/в | 2/в | 6/в | 6/в | 4/в | 1/а | 3/а | 8/а | 7/а |
|
| 2/в | 2/в | 4/в | 2/в | 4/в | 4/в | 2/в | 9/с | 9/с |
|
| 5/а | 5/а | 3/а | 8/а | 7/а | 4/в | 2/в | 6/в | 7/а |
| а | в | с | d |
Классы трехэквивалентных состояний a ={1,3,5,7,8}, b ={2,4}, c ={6}, d ={9} перекодируем по новым состояниям и выделим классы четырехэквивалентных состояний
|
|
|
Таблица переходов
| а | в | с | d | ||||||
|
| 2/в | 2/в | 6/с | 6/с | 4/в | 1/а | 3/а | 8/а | 7/а |
|
| 2/в | 2/в | 4/в | 2/в | 4/в | 4/в | 2/в | 9/d | 9/d |
|
| 5/а | 5/а | 3/а | 8/а | 7/а | 4/в | 2/в | 6/с | 7/а |
| а | в | а | c | d | e |
Перегруппируем таблицу перехода по новым классам a ={1,3,8}, b ={5,7}, c ={2,4}, d ={6}, е ={9}, перекодируем по новым состояниям.
Таблица переходов
| а | в | c | d | e | |||||
|
| 2/с | 2/с | 4/с | 6/d | 6/ d | 1/a | 3/a | 8/a | 7/b |
|
| 2/с | 2/с | 4/с | 4/c | 2/c | 4/c | 2/c | 9/e | 9/e |
|
| 5/в | 5/в | 7/в | 3/a | 8/a | 4/c | 2/c | 6/d | 7/b |
| а | в | c | d | e |
Так как внутри из каждого класса дальнейшее разбиение на классы не осуществляется, это означает, что найдены классы эквивалентных состояний :. a ={1,3,8}, b ={5,7}, c ={2,4}, d ={6}, е ={9}.
Минимизированный автомат Мили в новых состояниях имеет вид
Таблица переходов
| a | b | c | d | e | |
|
| с | d | a | a | b |
|
| с | c | c | e | e |
|
| в | c | c | d | b |
Таблица выходов
| a | b | c | d | e | |
|
| 1 | 1 | 0 | 0 | 0 |
|
| 0 | 0 | 1 | 0 | 0 |
|
| 0 | 0 | 1 | 1 | 1 |
