Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм минимизации автомата Мили


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

 

<== предыдущая лекция | следующая лекция ==>
Минимизация автоматов | Переход от автомата Мили к автомату Мура

Дата добавления: 2014-01-04; Просмотров: 385; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.005 сек.