Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 41
Текст из файла (страница 41)
Если для каждого состояния д некоторого ДКА создать блок, состоящий из д и эквивалентных ему состояний, то различные блоки состояний образуют разбиение множества состояний.~ Это значит, что каждое состояние может принадлежать 7 Нужно помнить, что один н тат же блок может формироваться несколько раз, начиная с резвых состояний. Однако рпбнение состоит нз различных блоков. так что каждый блок встречается в разбиении только один рп. ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 178 »олько одному блоку. Состояния из одного блока эквивалентны, а любые состояния, выбранные из разных блоков, не эквивалентны.
П Теперь можно кратко сформулировать алгоритм минимизации ДКА А = 1Е», Х, б, »уж Е). 1. Для выявления всех пар эквивалентных состояний применяем алгоритм заполнения таблицы. Разбиваем множество состояний Д на блоки взаимно эквивалентных состояний с помощью описанного выше метода. 3. Строим ДКА В с минимальным числом состояний, используя в качестве его состояний полученные блоки. Пусть у — функция переходов автомата В. Предположим, что 5 — множество эквивалентных состояний автомата А, а — входной символ. То- гда должен сушествовать один блок состояний Т, содержащий ~(»ь а) для всех состояний д из 5. Если это не так, то входной символ а переводит два состояния р и д из 5 в состояния, принадлежашие разныл» блокам согласно теореме 4.24.
Из этого можно сделать вывод, что состояния р и»! не были эквивалентныл»и и не могли вместе принадлежать 5. В результате определяется функция переходов )(5, а) = Т. Кроме того: а) начальным состоянием ДКА В является блок, содержащий начальное состояние автомата А; б) множеством допускаюших состояний автомата В является множество блоков, содержаших допускаюшие состояния ДКА А. Заметим, что если одно состояние в блоке является допускающим, то все остальные состояния этого блока также должны быть допускаюшими. Причина в том, что любое допускающее состояние отличимо от любого недопускаюшего, поэтому допускающее и недопускаюшее состояния не могут принадлежать одному блоку эквивалентных состояний. Пример 4.25.
Минимизируем ДКА, представленный на рис. 4.8. В примере 4.22 установлены блоки разбиения состояний. На рис. 4.12 изображен ДКА с минимальным числом состояний. Пять состояний этого автомата соответствуют пяти блокам эквивалентных состояний автомата на рис. 4.8. Начальным состоянием минимизированного автомата является !А, Е), так как А было начальным на рис.
4.8. Единственным допускающим — 1С), поскольку С вЂ” это единственное допускающее состояние на рис. 4.8. Заметим, что переходы на рис. 4.12 правильно отражают переходы на рис, 4.8. Например, на рис. 4.12 есть переход из !А, Е) в 1В, Н) по символу О. Это очевидно, так как А на рис. 4.8 переходит в В при чтении О, а Š— в О. Аналогично, при чтении 1 1А, Е) переходит в 1О, В ). По рис. 4.8 легко увидеть, что оба состояния А и Е переходят в Е по 1, так что для 1А, Е) состояние-преемник по 1 также выбрано правильно.
Тот факт, что ни А, ни Е не переходят в ьз по 1, неважен. Читатель может проверить, что и все остальные переходы изображены правильно. П 4.4. ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ 179 Начало Рис. 4.12. ДКА с минимальным числил~ состояний, эквнволентный автомату, изображенному на рис. 4.8 4.4.4. Почему минимизированный ДКА невозможно улучшить Предположим, что задан ДКА А, и мы минимизируем его до ДКА М с помощью метода разбиения из теоремы 4.24, Эта теорема показывает, что невозможно получить эквивалентный ДКА, группируя состояния автомата А в еще меньшее число групп. Но все же, может ли существовать другой ДКА эч', не связанный с А, который допускал бы тот же язык, что и автоматы А и М. но имел бы состояний меньше, чем автомат М? Методом от противного докажем, что такого автомата не существует. Сначала применим алгоритм различимости состояний из раздела 4,4.! к состояниям автоматов М и А' так, как если бы это был один автомат.
Можно предположить, что общих обозначений состояний у М и Аг нет, так что функция переходов комбинированного автомата будет объединением функций переходов автоматов М и А', которые между собой не пересекаются. Состояния комбинированного ДКА будут допускающими тогда и только тогда, когда они являются допускающими в соответствующих им автоматах. Начальные состояния автоматов М и Л' неразличимы, так как ЦМ) = Е(У).
Далее, если состояния (р, с?~ неразличимы, то для любого входного символа их преемники также неразличимы. Если бы преемников можно было различить, то р и с также можно было различить. Минимизация состояний НКА Может показаться, что метод разбиения состояний, минимизирующий ДКА, применим и для построения НКА с минимальным числом состояний, эквивалентного данному НКА или ДКА. Хотя методом полного перебора можно найти НКА с наименьшим количеством состояний, допускающий данный язык, просто сгруппировать состояния некоторого заданного НКА для этого языка нельзя.
ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 180 Пример приведен на рис. 4.13. Никакие из трех состояний не являются эквивалентнымн. Очевидно, что допускающее состояние В отличается от недопускаюших состояний А н С. Состояния А и С различаются входным символом О. С переходит в (А ) (недопускаюшее), тогда как А переходит в (А, В), которое включает допускаюшее состояние. Таким образом, группирование состояний не уменьшает количества состояний на рис. 4.13. Однако можно построить меньший НКА для этого же языка, просто удалив состояние С, Заметим, что А и В (без С) допускают все цепочки, которые заканчиваются нулем, а добавление С не позволяет допускать другие цепочки. вд Начало Рис.
4. 13. Нлл, который невоэмоэкно минимизировать с помощью эквивалентности состоянии Нн М ни М не могут иметь недостижимых состояний, иначе, исключив это состояние, можно было бы получить еше меньший ДКА для того же языка. Следовательно, каждое состояние автомата М неотличимо хотя бы от одного состояния автомата М Выясним, почему зто так.
Пусть р — состояние автомата М. Тогда суэцествует цепочка аэам..аь переводящая М из начального состояния в р. Эта цепочка также переводит эн' из начального в некоторое состояние су. Из того, что начальные состояния этих автоматов неразличимы, следует, что состояния-преемники, соответствующие входному символу аь также неразличимы. Состояния, следуюшие за этими состояниями при чтении а„также будут неразличимыми, и так далее, пока мы не придем к заключению, что состояния р и с) неразличимы. Поскольку автомат лГ содержит меньше состояний, чем М, то должны существовать лва состояния автомата М, которые неотличимы от одного и того же состояния автомата У.
Значит, эти состояния неразличимы. Но автомат М построен таким образом„что все его состояния отличимы друг от друга. Противоречие. Следовательно, предположение о сушествовании Ф неверно, н М действительно является ДКА с наименьшим количеством состояний среди всех ДКА, эквивалентных А.
Формально доказана следующая теорема. Теорема 4.26. Если из некоторого ДКА А с помощью алгоритма, описанного в теореме 4.24, построен ДКА М, то М имеет наименьшее число состояний из всех ДКА, эквивалентных А. ЕЗ Можно сформулировать более сильное утверждение, чем теорема 4.2б. Между состояввямя любого минимального ДКА Ж и состояниями ДКА М должно сушествовать взаимно 4.4, ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ 181 4.4.5. Упражнения к разделу 4.4 4.4.1. (» ) На рис. 4.14 представлена таблица переходов некоторого ДКА: а) составьте таблицу различимости для этого автомата; б) постройте эквивалентный ДКА с минимальным числом состояний.
Рнс. 4.14 ДКА, который нунсно минимизировать Выполните упражнение 4.4.1 для ДКА, представленного на рис. 4.15. Рис. 445. Еи»е ооин Д!»А, который нунсно тинииизировать (!!) Пусть р и»( — пара различимых состояний заданного ДКА А с и состояния- ми.
Какой может быль самая точная верхняя граница длины кратчайшей цепоч- ки, различающей р и»з, как функция от н? 4,4.3. ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 182 однозначное соответствие. Как уже доказано, каждое состояние М эквивалентно одному сосюянию Л», и ни одно состояние М не может быть эквивалентным двум сосгояниям Л». Аналогично можно доказать, что ни одно состояние Ф не может быть эквивалентным двум состояниям М, хотя каждое состояние автомата !У должно быть эквивалентно одному из состояний ДКА М.
Следовательно, существует только один ДКА с минимальным количеством состояний, эквивалентный А (с точностью до обозначений состояний). Резюме в зТазсиа о накачке, Если язык регулярен, то в каждой достаточно длинной цепочке эюго языка есть непустая подцепочка, которую можно 'накачать", т.е, повторить произ- вольное число раз; получаемые при этом цепочки будут принадлежать данному языку. Эта лемма используется для доказательства нерегулярности многих языков. в Операиии, сохраняющие регулярностль языков. Существует много операций, ре- зультат применения которых к регулярным языкам также является регулярным языком. В их числе объединение, конкатенация, замыкание (итерация), пересече- ние, дополнение, разность, обращение, гомоморфизм (замена каждого символа соответствующей цепочкой) и обратный гомоморфизм.
в Проверка нустаты регулярного языка, Существует алгоритм, который по такому заданному предо~велению регулярного языка, как автомат или регулярное выра- жение, определяет, является ли представленный язык пустым множеством. в Проверка принадлежноани регулярному языку. Существуез ачгоритм, который по заданной цепочке и некоторому представлению регулярного языка определяет, принадлежит ли цепочка языку. Ф Проверка различимости состояний. Два состояния некоторого ДКА различимы, если существует входная цепочка, которая переводит в допускающее только одно из этих состояний. Если начать с того, что все пары, состоящие из допускающего и недопускающего состояний, различимы, и найти дополнительные пары, которые по одному символу переходят в различимые состояния, можно обнаружить все пары различимых состояний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
