dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 39
Текст из файла (страница 39)
Если ДКА заканчивает в допускающем состоянии, то цепочка w принадлежитэтому языку, в противном случае — нет. Этот алгоритм является предельно быстрым.Если |w| = n и ДКА представлен с помощью подходящей структуры данных, например,двухмерного массива (таблицы переходов), то каждый переход требует постоянноговремени, а вся проверка занимает время O(n).Если L представлен способом, отличным от ДКА, то преобразуем это представление вДКА и применим описанную выше проверку. Такой подход может занять время, экспоненциально зависящее от размера данного представления и линейное относительно |w|.Однако, если язык задан с помощью НКА или ε-НКА, то намного проще и эффективнеенепосредственно проимитировать этот НКА. Символы цепочки w обрабатываются поодному, и запоминается множество состояний, в которые НКА может попасть после170Стр.
170ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂпрохождения любого пути, помеченного префиксом цепочки w. Идея такой имитациибыла представлена на рис. 2.10.Если длина цепочки w равна n, а количество состояний НКА равно s, то время работыэтого алгоритма равно O(ns2). Чтобы обработать очередной входной символ, необходимовзять предыдущее множество состояний, число которых не больше s, и для каждого изних найти следующее состояние. Затем объединяем не более s множеств, состоящих изне более, чем s состояний, для чего нужно время O(s2).Если заданный НКА содержит ε-переходы, то перед тем, как начать имитацию, необходимо вычислить ε-замыкание.
Такая обработка очередного входного символа a состоит из двух стадий, каждая из которых занимает время O(s2). Сначала для предыдущегомножества состояний находим последующие состояния при входе a. Далее вычисляем εзамыкание полученного множества состояний. Начальным множеством состояний длятакого моделирования будет ε-замыкание начального состояния НКА.И наконец, если язык L представлен регулярным выражением, длина которого s, то завремя O(s) можно преобразовать это выражение в ε-НКА с числом состояний не больше2s. Выполняем описанную выше имитацию, что требует O(ns2) времени для входной цепочки w длиной n.4.3.4. Óïðàæíåíèÿ ê ðàçäåëó 4.34.3.1.(∗) Приведите алгоритм определения, является ли регулярный язык L бесконечным. Указание.
Используйте лемму о накачке для доказательства того, что еслиязык содержит какую-нибудь цепочку, длина которой превышает определеннуюнижнюю границу, то этот язык должен быть бесконечным.4.3.2.Приведите алгоритм определения, содержит ли регулярный язык L по меньшеймере 100 цепочек.4.3.3.Пусть L — регулярный язык в алфавите Σ. Приведите алгоритм проверки равенства L = Σ*, т.е. содержит ли язык L все цепочки в алфавите Σ.4.3.4.Приведите алгоритм определения, содержат ли регулярные языки L1 и L2 хотябы одну общую цепочку.4.3.5.Пусть L1 и L2 — два регулярных языка с одним и тем же алфавитом Σ. Приведите алгоритм определения, существует ли цепочка из Σ*, которая не принадлежитни L1, ни L2.4.4.
Ýêâèâàëåíòíîñòü è ìèíèìèçàöèÿ àâòîìàòîâВ отличие от предыдущих вопросов — пустоты и принадлежности, алгоритмы решениякоторых были достаточно простыми, вопрос о том, определяют ли два представления двухрегулярных языков один и тот же язык, требует значительно больших интеллектуальных4.4. ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ È ÌÈÍÈÌÈÇÀÖÈß ÀÂÒÎÌÀÒÎÂСтр. 171171усилий. В этом разделе мы обсудим, как проверить, являются ли два описания регулярныхязыков эквивалентными в том смысле, что они задают один и тот же язык. Важным следствием этой проверки является возможность минимизации ДКА, т.е.
для любого ДКА можнонайти эквивалентный ему ДКА с минимальным количеством состояний. По существу, такой ДКА один: если даны два эквивалентных ДКА с минимальным числом состояний, товсегда можно переименовать состояния так, что эти ДКА станут одинаковыми.4.4.1. Ïðîâåðêà ýêâèâàëåíòíîñòè ñîñòîÿíèéНачнем с вопроса об эквивалентности состояний одного ДКА. Наша цель — понять,когда два различных состояния p и q можно заменить одним, работающим одновременнокак p и q. Будем говорить, что состояния p и q эквивалентны, если• для всех входных цепочек w состояние δˆ (p, w) является допускающим тогда итолько тогда, когда состояние δˆ (q, w) — допускающее.Менее формально, эквивалентные состояния p и q невозможно различить, если просто проверить, допускает ли автомат данную входную цепочку, начиная работу в одном (неизвестно,каком именно) из этих состояний.
Заметим, что состояния δˆ (p, w) и δˆ (q, w) могут и не совпадать — лишь бы оба они были либо допускающими, либо недопускающими.Если два состояния p и q не эквивалентны друг другу, то будем говорить, что ониразличимы, т.е. существует хотя бы одна цепочка w, для которой одно из состоянийδˆ (p, w) и δˆ (q, w) является допускающим, а другое — нет.Пример 4.18. Рассмотрим ДКА на рис.
4.8. Функцию переходов этого автомата обозначим через δ. Очевидно, что некоторые пары состояний не эквивалентны, например Cи G, потому что первое из них допускающее, а второе — нет. Пустая цепочка различаетэти состояния, так как δˆ (C, ε) — допускающее состояние, а δˆ (G, ε) — нет.НачалоРис. 4.8. Автомат с эквивалентными состояниями172Стр.
172ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂРассмотрим состояния A и G. Различить их с помощью цепочки ε невозможно, таккак оба они недопускающие. 0 также не различает их, поскольку по входу 0 автомат переходит в состояния B и G, соответственно, а оба эти состояния недопускающие. Однакоцепочка 01 различает A и G, так как δˆ (A, 01) = C, δˆ (G, 01) = E, состояние C — допускающее, а E — нет. Для доказательства неэквивалентности A и G достаточно любойвходной цепочки, переводящей автомат из состояний A и G в состояния, одно из которыхявляется допускающим, а второе — нет.Рассмотрим состояния A и E. Ни одно из них не является допускающим, так что цепочка ε не различает их. По входу 1 автомат переходит и из A, и из E в состояние F.
Таким образом, ни одна входная цепочка, начинающаяся с 1, не может различить их, поскольку δˆ (A, 1x) = δˆ (E, 1x) для любой цепочки x.Рассмотрим поведение в состояниях A и E на входах, которые начинаются с 0. Из состояний A и E автомат переходит в B и H, соответственно. Так как оба эти состояния недопускающие, сама по себе цепочка 0 не отличает A от E. Однако состояния B и H непомогут: по входу 1 оба эти состояния переходят в C, а по входу 0 — в G. Значит, ни одна входная цепочка, начинающаяся с 0, не может различить состояния A и E.
Следовательно, ни одна входная цепочка не различает состояния A и E, т.е. они эквивалентны. Для того чтобы найти эквивалентные состояния, нужно выявить все пары различимых состояний. Как ни странно, но если найти все пары состояний, различимых в соответствии с представленным ниже алгоритмом, то те пары состояний, которые найти неудастся, будут эквивалентными. Алгоритм, который называется алгоритмом заполнениятаблицы, состоит в рекурсивном обнаружении пар различимых состояний ДКАA = (Q, Σ, δ, q0, F).Базис. Если состояние p — допускающее, а q — не допускающее, то пара состояний{p, q} различима.Индукция.
Пусть p и q — состояния, для которых существует входной символ a,приводящий их в различимые состояния r = δ(p, a) и s = δ(q, a). Тогда {p, q} — пара различимых состояний. Это правило очевидно, потому что должна существовать цепочка w,отличающая r от s, т.е.
только одно из состояний δˆ (r, w) и δˆ (s, w) является допускающим. Тогда цепочка aw отличает p от q, так как δˆ (p, aw) и δˆ (q, aw) — это та же парасостояний, что и δˆ (r, w) и δˆ (s, w).Пример 4.19. Выполним алгоритм заполнения таблицы для ДКА, представленного нарис. 4.8. Окончательный вариант таблицы изображен на рис. 4.9, где x обозначает парыразличимых состояний, а пустые ячейки указывают пары эквивалентных состояний.Сначала в таблице нет ни одного x.В базисном случае, поскольку C — единственное допускающее состояние, записываем x в каждую пару состояний, в которую входит C. Зная некоторые пары различимыхсостояний, можно найти другие. Например, поскольку пара {C, H} различима, а состоя4.4. ÝÊÂÈÂÀËÅÍÒÍÎÑÒÜ È ÌÈÍÈÌÈÇÀÖÈß ÀÂÒÎÌÀÒÎÂСтр.
173173ния E и F по входу 0 переходят в H и C, соответственно, то пара {E, F} также различима.Фактически, все x на рис. 4.9, за исключением пары {A, G}, получаются очень просто:посмотрев на переходы из каждой пары состояний по символам 0 или 1, обнаружим (дляодного из этих символов), что одно состояние переходит в C, а другое — нет.
Различимость пары состояний {A, G} видна в следующем цикле, поскольку по символу 1 они переходят в F и E, соответственно, а различимость состояний {E, F} уже установлена.Рис. 4.9. Таблица неэквивалентности состоянийОднако обнаружить другие пары различимых состояний невозможно. Следовательно,оставшиеся три пары состояний {A, E}, {B, H} и {D, F} эквивалентны. Выясним, почемунельзя утверждать, что пара состояний {A, E} различима.
По входному символу 0 состояния A и E переходят в B и H, соответственно, а про эту пару пока неизвестно, различима она, или нет. По символу 1 оба состояния A и E переходят в F, так что нет никакойнадежды различить их этим способом. Остальные две пары, {B, H} и {D, F}, различитьнельзя, поскольку у них одинаковые переходы как по символу 0, так и по 1.
Таким образом, алгоритм заполнения таблицы останавливается на таблице, представленной нарис. 4.9, и корректно определяет эквивалентные и различимые состояния. Теорема 4.20. Если два состояния не различаются с помощью алгоритма заполнениятаблицы, то они эквивалентны.Доказательство. Снова рассмотрим ДКА A = (Q, Σ, δ, q0, F). Предположим, что утверждение теоремы неверно, т.е. существует хотя бы одна пара состояний {p, q}, для которой выполняются следующие условия.1.Состояния p и q различимы, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
