Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Недостижимые состояния




 

Среди состояний автомата могут быть такие, которые недостижимы из начального состояния ни для какой входной цепочки. На рис 3.8 (а) и 3.8 (в) таким является состояние 4. Такие состояния называются недостижимыми и столбцы, соответствующие этим состояниям, можно удалить, получив автомат с меньшим числом состояний.

Для любого конечного автомата довольно просто составляется список достижимых состояний:

1. Начать список начальным состоянием.

2. Для каждого состояния, уже включенного в список, добавить все еще не занесенные в него состояния, которые могут быть достигнуты из этого нового состояния под действием каждого входного символа.

Если эта процедура перестает давать новые состояния, то все достижимые состояния уже получены, а все остальные можно удалить как недостижимые. Число шагов процедуры ограничено числом состояний.

 

Пример 3.4. На рис. 3.9 (а) приведена таблица переходов автомата с начальным состоянием s0. Сформируем для него список достижимых состояний, по предложенному алгоритму. Вначале занесем в список s0. Затем добавим к нему s1 и s5. Из s1 имеется переход в s2 и s7, а из s5 - в s3 и s1, причем новым является только состояние s3. Из s2, s7 и s3 нет переходов в новые состояния, следовательно, окончательный список достижимых состояний

s0 s1 s5 s2 s7 s3.

Оставшиеся состояния s4, s6 и s8 - недостижимы. Удалив соответствующие им столбцы, получим таблицу, представленную на рис. 3.9 (б).

 

Будем говорить, что автомат приведенный (минимальный), если он не содержит недостижимых состояний и никакие два его состояния неэквивалентны друг другу.

 

Если автомат не приведенный, то можно получить эквивалентный ему автомат, с меньшим числом состояний, либо исключая недостижимые состояния, либо объединяя эквивалентные в одно состояние. Приведенный автомат, полученный таким способом, имеет число состояний меньшее, чем исходный (если он уже не был приведенным), и может быть компактно реализован на вычислительной машине.

Метод нахождения недостижимых состояний, приведенный выше, достаточно эффективен. Однако, использовать тест эквивалентности для минимизации автоматов нецелесообразно, так как он позволяет обработать одновременно только два состояния. Далее предлагается более эффективный способ поиска и объединения эквивалентных состояний.




Поделиться с друзьями:


Дата добавления: 2015-06-27; Просмотров: 2072; Нарушение авторских прав?; Мы поможем в написании вашей работы!


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



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




Генерация страницы за: 0.01 сек.