Минимизация абстрактных автоматов
Работа добавлена на сайт samzan.net:
38. Минимизация абстрактных автоматов.
Два абстрактных автомата с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установки их в начальное состояние a1 их реакции, т.е. выходные слова на любое входное слово совпадают. При этом автоматы могут иметь различное число внутренних состояний. Отсюда возникает задача нахождения среди множества эквивалентных автоматов минимального, т.е. с минимальным числом внутренних состояний.
Один из алгоритмов минимизации полностью определенного автомата заключается в следующем: 1. Множество состояний исходного абстрактного автомата разбивается на попарно непересекающиеся классы эквивалентных состояний. 2. Каждый класс эквивалентности заменяется одним состоянием. В результате получается минимальный автомат, имеющий столько же состояний, на сколько классов эквивалентности разбиваются исходные
состояния автомата. Для разбиения множества состояний автомата на попарно непересекающиеся классы эквивалентных состояний, сначала разбивают все состояния на классы одноэквивалентных состояний. Два состояния при этом считаются одноэквивалентными, если их реакции на любые входные буквы алфавита совпадают, т.е. соответствующие этим состояниям столбцы в таблице выходов совпадают. Далее производят разбиение состояний в пределах каждого класса одноэквивалентных состояний на классы двухэквивалентных состояний. При этом два одноэквивалентные состояния считаются двухэквивалентными, если они переводятся любым входным символом в одинаковые классы одноэквивалентных состояний. Далее производят разбиение двухэквивалентных состояний на классы трехэквивалентных состояний и т.д. пока этот процесс возможен. Поясним методику на примере минимизации автомата Мили. Исходные данные: таблица переходов и таблица выходов.
По таблице выходов видим что первый и шестой, второй и пятый, а также третий и четвертый столбцы образуют классы одноэквивалентных состояний. Составим таблицу классов одноэквивалентных состояний. Видно, что первый и второй, а так же третий и четвертый столбцы образуют классы двухэквивалентных состояний.
В таблице двухэквивалентных состояний вторую и четвертую строку можно вычеркнуть так как они дублируют первую и третью соответственно. Дальнешая же минимизация очевидно невозможна. Итак, запишем новые таблицы переходов и выходов минимизированного
автомата.
Для наглядности построим граф заданного автомата и минимизированного: :
Так же можем сравнить реакцию обоих автоматов на входные сигналы:
Как видим, минимизированный автомат работает абсолютно аналогично.
2. Предмет метод периодизация историография ИОГП
3. Юриспруденция Новосибирск 2008Кафедра трудового и земельного права И
4. Бухгалтерская отчетность организации
5. условий Они разделяются на следующие процессы- магматический пегматитовый гидротермальный
6. История России Темы контрольных работ
7. Рекреационные ресурсы Северного Кавказа и Кабардино-Балкарской Республики
8. Лидер года ~ 2013 В соответствии с утвержденным положением О проведении Городского конкурса лидеров и
9. Черничную Чайку Кто из них выиграет затянувшуюся дуэль и впишет свое имя в новейшую историю космического п
10. Реферат- Этногенез и технологии виртуальной реальности
11. февраля 1998 Структуры и формы поддержки инновационной деятельности Миннауки России разрабатывает совме
12. неоклассическая экономическая теория часто считают экономический либерализм
13. это совокупность знаний умений и навыков обеспечивающих автору речи незатрудненное построение речевых вы
14. Методы интеграции информатики с другими дисциплинами в школьном курсе
15. Лекция 10. Экономическая мысль России в 2030 гг.html
16. Бетонные работы
17. Технология и технологический процесс
18. Гранитназва установи ЗАТВЕРДЖЕНОнаказом Державного казначейства Українивід 18 гр
19. Судебная защита земельноимущественных прав для специальности- 080114.
20. Анализ фрагмента из фильма 99 франков