dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 40

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 40)

существует некоторая цепочка w, для которой только одно из состояний δˆ (p,w) и δˆ (q,w) является допускающим.2.Алгоритм заполнения таблицы не может обнаружить, что состояния p и q различимы.Назовем такую пару состояний плохой парой.Если существуют плохие пары, то среди них должны быть такие, которые различимыс помощью кратчайших из всех цепочек, различающих плохие пары. Пусть пара174Стр. 174ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ{p, q} — плохая, а w = a1a2…an — кратчайшая из всех цепочек, различающих p и q.

Тогда только одно из состояний δˆ (p, w) и δˆ (q, w) является допускающим.Заметим, что цепочка w не может быть ε, так как, если некоторая пара состояний различается с помощью ε, то ее можно обнаружить, выполнив базисную часть алгоритмазаполнения таблицы. Следовательно, n ≥ 1.Рассмотрим состояния r = δ(p, a1) и s = δ(q, a1). Эти состояния можно различить с помощью цепочки a2a3…an, поскольку она переводит r и s в состояния δˆ (p, w) и δˆ (q, w).Однако цепочка, отличающая r от s, короче любой цепочки, различающей плохую пару.Следовательно, {r, s} не может быть плохой парой, и алгоритм заполнения таблицы должен был обнаружить, что эти состояния различимы.Но индуктивная часть алгоритма заполнения таблицы не остановится, пока не придетк выводу, что состояния p и q также различимы, поскольку уже обнаружено, что состояние δ(p, a1) = r отличается от δ(q, a1) = s. Получено противоречие с предположением отом, что существуют плохие пары состояний. Но если плохих пар нет, то любую паруразличимых состояний можно обнаружить с помощью алгоритма заполнения таблицы, итеорема доказана.

†4.4.2. Ïðîâåðêà ýêâèâàëåíòíîñòè ðåãóëÿðíûõ ÿçûêîâЭквивалентность регулярных языков легко проверяется с помощью алгоритма заполнения таблицы. Предположим, что языки L и M представлены, например, один — регулярнымвыражением, а второй — некоторым НКА. Преобразуем каждое из этих представлений вДКА. Теперь представим себе ДКА, состояния которого равны объединению состояний автоматов для языков L и M. Технически этот ДКА содержит два начальных состояния, нофактически при проверке эквивалентности начальное состояние не играет никакой роли,поэтому любое из этих двух состояний можно принять за единственное начальное.Далее проверяем эквивалентность начальных состояний двух заданных ДКА, используяалгоритм заполнения таблицы. Если они эквивалентны, то L = M, а если нет, то L ≠ M.Пример 4.21.

Рассмотрим два ДКА (рис. 4.10). Каждый ДКА допускает пустую цепочку и все цепочки, которые заканчиваются символом 0, т.е. язык регулярного выражения ε + (0 + 1)*0. Можно представить, что на рис. 4.10 изображен один ДКА, содержащий пять состояний от A до E.

Если применить алгоритм заполнения таблицы к этомуавтомату, то в результате получим таблицу, представленную на рис. 4.11.Чтобы заполнить эту таблицу, начнем с размещения x в ячейках, соответствующихтем парам состояний, из которых только одно является допускающим. Оказывается, чтобольше делать ничего не нужно. Остальные четыре пары {A, C}, {A, D}, {C, D} и {B, E}являются парами эквивалентных состояний. Необходимо убедиться, что в индуктивнойчасти алгоритма заполнения таблицы различимые состояния не обнаружены. Например,с помощью такой таблицы (см. рис.

4.11) нельзя различить пару {A, D}, так как по символу 0 эти состояния переходят сами в себя, а по 1 — в пару состояний {B, E}, которая4.4. ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ È ÌÈÍÈÌÈÇÀÖÈß ÀÂÒÎÌÀÒÎÂСтр. 175175осталась неразличимой. Поскольку в результате проверки установлено, что состояния Aи C эквиваленты и являются начальными у двух заданных автоматов, делаем вывод, чтоэти ДКА действительно допускают один и тот же язык. †НачалоНачалоРис.

4.10. Два эквивалентных ДКАРис. 4.11. Таблица различимости для автоматов, представленных на рис. 4.10Время заполнения таблицы, а значит и время проверки эквивалентности двух состояний, полиномиально относительно числа состояний. Если число состояний равно n, токоличество пар состояний равно ( n2 ) , или n(n – 1)/2. За один цикл рассматриваются всепары состояний, чтобы определить, является ли одна из пар состояний-преемников различимой.

Значит, один цикл занимает время не больше O(n2). Кроме того, если в некотором цикле не обнаружены новые пары различимых состояний, то алгоритм заканчивается. Следовательно, количество циклов не превышает O(n2), а верхняя граница временизаполнения таблицы равна O(n4).Однако с помощью более аккуратно построенного алгоритма можно заполнить таблицу за время O(n2). С этой целью для каждой пары состояний {r, s} необходимо составить список пар состояний {p, q}, “зависящих” от {r, s}, т.е., если пара {r, s} различима,то {p, q} также различима. Вначале такие списки создаются путем рассмотрения каждой176Стр.

176ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂпары состояний {p, q}, и для каждого входного символа a (а их число фиксировано) пара{p, q} вносится в список для пары состояний-преемников {δ(p, a), δ(q, a)}.Если обнаруживается, что пара {r, s} различима, то в списке этой пары каждая поканеразличимая пара отмечается как различимая и помещается в очередь пар, списки которых нужно проверить аналогичным образом.Общее время работы этого алгоритма пропорционально сумме длин списков, так каккаждый раз либо что-то добавляется в списки (инициализация), либо в первый и последний раз проверяется наличие некоторой пары в списке (когда проходим по списку пары,признанной различимой).

Так как размер входного алфавита считается постоянным, токаждая пара состояний попадает в O(1) списков. Поскольку всего пар O(n2), суммарноевремя также O(n2).4.4.3. Ìèíèìèçàöèÿ ÄÊÀЕще одним важным следствием проверки эквивалентности состояний является возможность “минимизации” ДКА. Это значит, что для каждого ДКА можно найти эквивалентный ему ДКА с наименьшим числом состояний. Более того, для данного языка существует единственный минимальный ДКА (с точностью до выбираемого нами обозначения состояний).Основная идея минимизации ДКА состоит в том, что понятие эквивалентности состояний позволяет объединять состояния в блоки следующим образом.1.Все состояния в блоке эквиваленты.2.Любые два состояния, выбранные из разных блоков, неэквивалентны.Пример 4.22.

Рассмотрим рис. 4.9, на котором представлены эквивалентность и различимость для состояний, изображенных на рис. 4.8. Эти состояния разбиваются на эквивалентные блоки следующим образом: ({A, E}, {B, H}, {C}, {D, F}, {G}). Заметим, чтокаждая пара эквивалентных состояний помещена в отдельный блок, а состояния, отличимые от всех остальных, образуют отдельные блоки.Для автомата, представленного на рис.

4.10, разбиение на блоки имеет вид ({A, C, D},{B, E}). Этот пример показывает, что в блоке может быть более двух состояний. Можетпоказаться случайностью, что состояния A, C и D помещены в один блок потому, чтокаждые два из них эквивалентны и ни одно из этих состояний не эквивалентно еще какому-нибудь состоянию, кроме этих. Однако следующая теорема утверждает, что такая ситуация следует из определения эквивалентности состояний. †Теорема 4.23.

Эквивалентность состояний транзитивна, т.е., если для некоторогоДКА A = (Q, Σ, δ, q0, F) состояние p эквивалентно q, а q — r, то состояния p и r такжеэквивалентны.Доказательство. Естественно ожидать, что любое отношение, называемое “эквивалентностью”, обладает свойством транзитивности. Однако, просто назвав какое-то от4.4. ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ È ÌÈÍÈÌÈÇÀÖÈß ÀÂÒÎÌÀÒÎÂСтр. 177177ношение “эквивалентностью”, нельзя гарантировать, что оно транзитивно — это нужно доказать.Предположим, что {p, q} и {q, r} — пары эквивалентных состояний, а пара {p, r} —различима.

Тогда должна существовать такая цепочка w, для которой только одно из состояний δˆ (p, w) и δˆ (r, w) является допускающим. Используя симметрию, предположим,что δˆ (p, w) — допускающее.Теперь посмотрим, будет ли состояние δˆ (q, w) допускающим. Если оно допускающее, то пара {q, r} различима, так как состояние δˆ (q, w) —допускающее, а δˆ (r, w) —нет. Если δˆ (q, w) не допускающее, то по аналогичным причинам пара {p, q} различима.Полученное противоречие доказывает неразличимость пары {p, r}, т.е. состояния p и rэквивалентны. †Теорему 4.23 можно использовать для обоснования очевидного алгоритма разбиениясостояний.

Для каждого состояния q строится блок, состоящий из q и всех эквивалентных ему состояний. Необходимо доказать, что результирующие блоки образуют разбиение множества состояний, т.е. ни одно состояние не принадлежит двум разным блокам.Сначала заметим, что состояния внутри каждого блока взаимно эквивалентны, т.е.,если p и r принадлежат блоку состояний, эквивалентных q, то согласно теореме 4.23 ониэквивалентны.Предположим, что существуют два пересекающихся, но не совпадающих блока, т.е.существует блок B, содержащий состояния p и q, и блок C, который содержит p, но не q.Поскольку состояния p и q принадлежат одному блоку, то они эквивалентны. Рассмотрим возможные варианты построения блока C.

Если этот блок образован состоянием p,то q было бы в блоке C, так как эти состояния эквивалентны. Следовательно, существуетнекоторое третье состояние s, порождающее блок C, т.е. C — это множество состояний,эквивалентных s.Состояния p и s эквивалентны, так как оба принадлежат C. Также p эквивалентно q,потому что оба эти состояния принадлежат B. Согласно свойству транзитивности, доказанному в теореме 4.23, состояние q эквивалентно s. Но тогда q принадлежит блоку C,что противоречит предположению о существовании пересекающихся, но не совпадающих блоков. Итак, эквивалентность состояний задает их разбиение, т.е. любые два состояния имеют или совпадающие, или не пересекающиеся множества эквивалентных имсостояний.

Следующая теорема подытоживает результаты проведенного анализа.Теорема 4.24. Если для каждого состояния q некоторого ДКА создать блок, состоящий из q и эквивалентных ему состояний, то различные блоки состояний образуют разбиение множества состояний.7 Это значит, что каждое состояние может принадлежать7Нужно помнить, что один и тот же блок может формироваться несколько раз, начиная с разных состояний. Однако разбиение состоит из различных блоков, так что каждый блок встречаетсяв разбиении только один раз.178Стр.

Характеристики

Список файлов книги