Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 40
Текст из файла (страница 40)
1. Состояния р и д различимы, т.е, существует некоторая цепочка эе, для которой толь- ко одно из состояний 6 (р,чо) и Б (д,ж) является допускаюшим. 2. Алгоритм заполнения таблицы не может обнаружить, что состояния р и д различимы. Назовем такую пару состояний пчохой парой. Если существуют плохие пары, то среди них должны быть такие, которые различимы с помощью кратчайших из всех цепочек, различающих плохие пары. Пусть пара ГЛАВА 4.
СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 174 (Р, ф — плохая, а и = а~ам..а„— кратчайшая из всех цепочек, различающих р и и. То- гда только одно из состояний д (р, и ) и 8 (и, ж) является допускающим. Заметим, что цепочка ж не может быть а, так как, если некоторая пара состояний различается с помощью а то ее можно обнаружить, выполнив базисную часть алгоритма заполнения таблицы. Следовательно, и > 1. Рассмотрим состояния г = с(р, а,) и з = Щ а~). Эти состояния можно различить с помощью цепочки д ад..а„, поскольку она переводит г и я в состояния 6 (р,м) и 8 (д,в). Однако цепочка, отличающая г от ж короче любой цепочки, различающей плохую пару.
Следовательно, («, з) не может быть плохой парой, и алгоритм заполнения таблицы должен был обнаружить, что эти состояния различимы. Но индуктивная часть алгоритма заполнения таблицы не остановится, пока не придет к выводу, что состояния р и и также различимы, поскольку уже обнаружено, что состояаие с(р, а,) = г отличается от фд, а~) = з. Получено противоречие с предположением о том, что существуют плохие пары состояний.
Но если плохих пар нет, то любую пару различимых состояний можно обнаружить с помощью алгоритма заполнения таблицы, и теорема доказана. СЗ 4.4.2. Проверка эквивалентности Регулярных языков Эквивалентность регулярных языков легко проверяется с помощью алгоритма заполнения таблицы. Предположим, что языки 1 и М представлены, например, один — регулярным выражением, а второй — некоторым НКА. Преобразуем каждое из этих представлений в ДКА. Теперь представим себе ДКА, состояния которого равны обьединению состояний автоматов для языков 1 и М. Технически этот ДКА содержит два начальных состояния, но фактически при проверке эквивалентности начальное состояние не играет никакой роли, поэтому любое из этих двух состояний можно принять за единственное начальное.
Далее проверяем эквивалентность начальных состояний двух заданных ДКА, используя алгоритм заполнения таблицы. Если они эквивалентны, то 1 = М, а если нет, то 1 и М. Пример 4.21. Рассмотрим два ДКА (рис. 4.! 0). Каждый ДКА допускает пустую цепочку и все цепочки, которые заканчиваются символом О, т.е.
язык регулярного выражения е '- (О + 1) О. Можно представить, что на рис. 4.10 изображен один ДКА, содержащий пять состояний от А до Е. Если применить алгоритм заполнения таблицы к этому автомату, то в результате получим таблицу, представленную на рис. 4.1!. Чтобы заполнить эту таблицу, начнем с размещения х в ячейках, соответствующих тем парам состояний, из которых только одно является допускающим. Оказывается, что больше делать ничего не нужно. Остальные четыре пары (А, С), (А, О), (С, Р) и (В, Е) являются парами эквивалентных состояний. Необходимо убедиться, что в индуктивной части алгоритма заполнения таблицы различимые состояния не обнаружены.
Например, с помощью такой таблицы (см. рис. 4.11) нельзя различить пару (А„В), так как по символу 0 эти состояния переходят сами в себя, а по ! — в пару состояний (В, Е), которая 4.4. ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ осталась неразличимой. Поскольку в результате проверки установлено, что состояния А и С эквиваленты и являются начальными у двух заданных автоматов, делаем вывод, что эти ДКА действительно допускают один и тот же язык. П Начал Нача Рис.
4.10. Два зквивалентнылДКА А В С О Рис. 411. Таблица различимости для автоматов, представленных на рнс. 410 Время заполнения таблицы, а значит и время проверки эквивалентности двух состояний, полиномиально относительно числа состояний. Если число состояний равно п, то количество пар состояний равно (г), или п(п — 1)12. За один цикл рассматриваются все пары состояний„ чтобы определить, является ли одна из пар состояний-преемников различимой. Значит, один цикл занимает время не больше 0(п ), Кроме того, если в некотором цикле не обнаружены новые пары различимых состояний, то алгоритм заканчивается. Следовательно, количество циклов не превышает 0(п ), а верхняя граница времени г заполнения таблицы равна 0(пл).
Однако с помощью более аккуратно построенного алгоритма можно заполнить таблицу за время 0(пг). С этой целью для каждой пары состояний (г, л) необходимо составить список пар состояний (р, о), "зависящих" от (г, л), т,е., если пара (г, л) различима, то (Р, с)) также различима. Вначале такие списки создаются путем рассмотрения каждой ГЛАВА 4. СВОИСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 176 пары состояний 1р, 9), и для каждого входного символа а (а их число фиксировано) лара 1р, 9) вносится в список дпя пары состояний-преемников 1о1р, а), о19, а)) . Если обнаруживается, что пара (г, з) различима, то в списке этой пары каждая пока неразличимая пара отмечается как различимая и помещается в очередь пар, списки которых нужно проверить аналогичным образом.
Общее время работы этого алгоритма пропорционально сумме длин списков, так как каждый раз либо что-то добавляется в списки (инициализация), либо в первый н последний раз проверяется наличие некоторой пары в списке (когда проходим по списку пары, прюпанной различимой). Так как размер входного алфавита считается постоянным, то каждая пара состояний попадает в О(!) списков. Поскольку всего пар 0(п~), суммарное время также 0(п~).
4.4.3. Минимизация ДКА Еще одним важным следствием проверки эквивалентности состояний является возможность "минимизации" ДКА. Это значит, что для каждого ДКА можно найти эквивалентный ему ДКА с наименьшим числом состояний. Более того, для данного языка существует единственный минимальный ДКА (с точностью до выбираемого нами обозначеппя состояний), Основная идея минимизации ДКА состоит в том, что понятие эквивалентности состояний позволяет объединять состояния в блоки следующим образом. 1.
Все состояния в блоке эквиваленты. 2. Любые два состояния, выбранные из разных блоков, пеэквивалентны. Пример 4.22. Рассмотрим рис. 4.9, на котором представлены эквивалентность и разлпчпмость для состояний, изображенных на рис. 4.8. Эти состояния разбиваются на эквивалентные блоки следующим образом: (1А, Е), 1В, Н), 1С), (О, Е), 10)). Заметим, что каждая пара эквивалентных состояний помещена в отдельный блок, а состояния, отличпмые от всех остальных, образуют отдельные блоки.
Для автомата, представленного на рис. 4.10, разбиение на блоки имеет вид (1А, С, О), 1В, Е)). Этот пример показывает, что в блоке может быть более двух состояний. Может показаться случайностью, что состояния А, С и 0 помещены в один блок потому, что каждые два из них эквивалентны и ни одно из этих состояний не эквивалентно еше какочу-нибудь состоянию, кроме этих. Однако следующая теорема утверждает, что такая ситуация следует из определения эквивалентности состояний. П Теорема 4.23.
Эквивалентность состояний транзитивна, т.е., если для некоторого ДКА А = Я, Х, б, дщ г) состояние р эквивалентно д, а д — г, то состояния р и г также эквивалентны. Доказательство. Естественно ожидать, что любое отношение, называемое "эквивалентностью", обладает свойством транзитивности. Однако, просто назвав какое-то от- 177 4.4.
ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ ношение "эквивалентностью", нельзя гарантировать, что оно транзитивно — это нуж- но доказать. Предположим, что (р, су) и (~7, г) — пары эквивалентных состояний, а пара (р, г)— различима. Тогда должна существовать такая цепочка н, для которой только одно из состояний а (р, ч ) и б (г, м) является допускающим.
Используя симметрию, предположим, что а (р, и) — допускающее, Теперь посмотрим, будет ли состояние Б (д, ч) допускающим. Если оно допускающее, то пара (д, г) различима, так как состояние а (д, ж) — допускающее, а а (», ж)— нет. Если б (д, м) не допускающее, то по аналогичным причинам пара (р, ф различима.
Полученное противоречие доказывает неразличимость пары (р, г), т.е. состояния р и г эквивалентны. П Теорему 4.23 можно использовать для обоснования очевидного алгоритма разбиения состояний. Для каждого состояния д строится блок, состоящий из д и всех эквивалентных ему состояний. Необходимо доказать, что результирующие блоки образуют разбиение множества состояний, т.е. ни одно состояние не принадлежит двум разным блокам, Сначала заметим, что состояния внутри каждого блока взаимно эквивалентны, т.е., если р и г принадлежат блоку состояний, эквивалентных д, то согласно теореме 4.23 они эквивалентны.
Предположим, что существуют два пересекающихся, но не совпадающих блока, т.е. существует блок В, содержащий состояния р и д, и блок С, который содержит р, но не ~у. Поскольку состояния р и су принадлежат одному блоку, то они эквивалентны. Рассмотрим возможные варианты построения блока С. Если этот блок образован состоянием р, то д было бы в блоке С, так как этн состояния эквивалентны. Следовательно, существует некоторое третье состояние е, порождающее блок С, т.е. С вЂ” это множество состояний, эквивалентныхж Состояния р и з эквивалентны, так как оба принадлежат С. Также р эквивалентно ~7, потому что оба эти состояния принадлежат В.
Согласно свойству транзитивности, доказанному в теореме 4.23, состояние 7 эквивалентно д Но тогда д принадлежит блоку С, что противоречит предположению о существовании пересекающихся, но не совпадающих блоков. Итак, эквивалентность состояний задает их разбиение, т.е. любые два со- стояния имеют или совпадающие, илн не пересекающиеся множества эквивалентных им состояний. Следующая теорема подытоживает результаты проведенного анализа. Теорема 4.24.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
