Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 39
Текст из файла (страница 39)
Этот алгоритм является предельно быстрым. Если ~н ~ = и и ДКА представлен с помощью подходящей структуры данных, например, двухмерного массива (таблицы переходов), то каждый переход требует постоянного времени, а вся проверка занимает время О(п). Если ь представлен способом, отличным от ДКА, то преобразуем это представление в ДКА и применим описанную выше проверку.
Такой подход может занять время, экспоненциально зависящее от размера данного представления и линейное относительно (и(. Однако, если язык задан с помощью НКА или я-НКА, то намного проще и эффективнее непосредственно првимнтировать этот НКА. Символы цепочки и обрабатываются по одному, и запоминается множество состояний, в которые НКА может попасть после ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 170 прохождения любого пути, помеченного префиксам цепочки зг.
Идея такой имитации была представлена на рис. 2.10. Если длина цепочки и равна л, а количество состояний НКА равно ж то время работы зтого алгоритма равно 0(из~). Чтобы обработать очередной входной символ, необходимо взять предыдущее множество состояний, число которых не больше ж и для каждого из явх найти следующее состояние. Затем объединяем не более з множеств, состоящих из ве более, чем з состояний, для чего нужно время 0(з ).
Если заданный НКА содержит в-переходы, то перед тем, как начать имитацию, необходимо вычислить в-замыкание. Такая обработка очередного входного символа а состоят нз двух стадий, каждая из которых занимает время 0(з~). Сначала для предыдущего киожества состояний находим последующие состояния при входе а. Далее вычисляем взаныкание полученного множества состояний. Начальным множеством состояний для такого моделирования будет в-замыкание начального состояния НКА. И наконец, если язык Е представлен регулярным выражением, длина которого ж то за время 01з) можно преобразовать это выражение в в-НКА с числом состояний не больше м. Выполняем описанную выше имитацию, что требует О(из~) времени для входной цепочки ж длиной и.
4.3.4. упражнения к разделу 4.3 4.3.1. (ь) Приведите алгоритм определения, является ли регулярный язык Е бесконечным. Указание. Используйте лемму о накачке для доказательства того, что если язык содержит какую-нибудь цепочку, длина которой превышает определенную нижнюю границу, то этот язык должен быть бесконечным. 4.3.2.
Приведите алгоритм определения, содержит ли регулярный язык Е по меньшей мере 100 цепочек. 43.3. Пусть Š— регулярный язык в алфавите Х. Приведите алгоритм проверки равенства Е = Х, т.е, содержит ли язык Е все цепочки в алфавите Х. 4.3.4. Приведите алгоритм определения, содержат ли регулярные языки Е~ и Ет хотя бы одну общую цепочку. 4.35, Пусть Е, и Ез — два регулярных языка с одним и тем же алфавитом Х. Приведите алгоритм определения, существует ли цепочка из Х, которая не принадлежит нн Еь нн Ел 4.4. Эквивалентность и минимизация автоматов В отличие от предыдущих вопросов — пустоты и принадлежности, алгоритмы решения которых были достаточно простыми, вопрос о том, определяют ли два представления двух регулярных языков один и тот же язык, требует значительно больших интеллектуальных 171 4.4.
ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ усилий. В этом разделе мы обсудим, как проверить, являются ли два описания регулярных языков эквивалентными в том смысле, что они задают один и тот же язык. Важным следствием этой проверки является возможность минимизации ДКА, т.е. для любого ДКА можно найти эквивалентный ему ДКА с минимальным количеством состояний. По существу, такой ДКА олин: если даны два эквивалентных ДКА с минимальным числом состояний, то всегда можно переименовать состояния так, что эти ДКА станут одинаковыми. 4.4.1. Проверка эквивалентности состояний Начнем с вопроса об эквивалентности состояний одного ДКА. Наша цель — понять, когда два различных состояния р и е) можно заменить одним, работающим одновременно как р и еу.
Будем говорить, что состояния р и е) эквивалентны, если ° для всех входных цепочек эе состояние 8 (р,эе) является допускающим тогда и только тогда, когда состояние 8 (д, эе) — допускающее. Менее формально, эквивалентные состояния р и су невозможно различить, если просто проверить, допускает ли автомат данную входную цепочку, начиная работу в одном (неизвестно, каком именно) из этих состояний, Заметим, что состояния 8 (р, ж) и д (е), ж) могут и не совпадать — лишь бы оба они были либо допускающими, либо недопускающими. Если два состояния р и д не эквивалентны друг другу, то будем говорить, что они различимы, т.е, существует хотя бы одна цепочка эе, для которой одно из состояний 8 (р, и) и 6 (4, эе) является допускающим, а другое — нет. Пример 4.18.
Рассмотрим ДКА на рис. 4.8. Функцию переходов этого автомата обозначим через б. Очевидно, что некоторые пары состояний не эквивалентны, например С и б, потому что первое из них допускающее, а второе — нет. Пустая цепочка различает эти состояния, так как 8 (С, а) — допускающее состояние, а 8 (л, в) — нет. Начал Рис 48. Автомат с эквивалентными состолнинми ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 172 Рассмотрим состояния А и О.
Различить их с помощью цепочки в невозможно, так кзк оба они недопускаюшие. 0 также не различает их, поскольку по входу 0 автомат переходит в состояния В и С, соответственно, а оба эти состояния недопускаюшие. Однако цепочка 01 различает А и б, так как б (А, 01) = С, б (б, 01)= Е, состояние С вЂ” допускающее, а Š— нет. Для доказательства неэквивалентности А и б достаточно любой входной цепочки, переводящей автомат из состояний А и б в состояния, одно из которых является допускающим, а второе — нет. Рассмотрим состояния А и Е.
Ни одно из них не является допускающим, так что цепочка вне различает их. По входу 1 автомат переходит и из А, и из Е в состояние Е. Таким образом, ни одна входная цепочка, начинающаяся с 1, не может различить их, поскольку б (А, 1х) = б (Е, 1х) для любой цепочки х. Рассмотрим поведение в состояниях А и Е на входах, которые начинаются с О. Из состояний А и Е автомат переходит в В и Н, соответственно. Так как оба эти состояния недопусьаюшие, сама по себе цепочка 0 не отличает А от Е.
Однако состояния В и Н не помогут: по входу 1 оба эти состояния переходят в С, а по входу 0 — в О. Значит, ни одна входная цепочка, начинающаяся с О, не может различить состояния А и Е. Следовательно, ни одна входная цепочка не различает состояния А и Е, т.е. они эквивалентны. П Для того чтобы найти эквивалентные состояния, нужно выявить все пары различииых состояний. Как ни странно, но если найти все пары состояний, различимых в соответствии с представленным ниже алгоритмом, то те пары состояний, которые найти не удастся, будут эквивалентными. Алгоритм, который называется алгоритмом заполнения мабливы, состоит в рекурсивном обнаружении пар различимых состояний ДКА А = (Ы Е, б, Чо, Е). Базис.
Если состояние р — допускающее, а д — не допускающее, то пара состояний (р, 4) различима. Индукции, Пусть р и д — состояния, для которых существует входной символ а, приводящий их в различимые состояния г = сяр, а) и з = с(су, а). Тогда (р, ф — пара различимых состояний. Это правило очевидно, потому что должна существовать цепочка и, отличающая г от з, т.е, только одно из состояний б (г, и ) и б (ж н ) является допускающим. Тогда цепочка аж отличает р от д, так как б (р, ан) и б (д, аи) — это та же пара состояний, что и б (г, н ) и 8 (ж н ). Пример 4.19.
Выполним алгоритм заполнения таблицы для ДКА, представленного на ркс. 4.8. Окончательный вариант таблицы изображен на рис. 4.9, где х обозначает пары различимых состояний, а пустые ячейки указывают пары эквивалентных состояний. Сначала в таблице нет ни одного х. В базисном случае, поскольку С вЂ” единственное допускающее состояние, записываем х в каждую пару состояний, в которую входит С. Зная некоторые пары различимых состояний, можно найти другие. Например, поскольку пара (С, Н) различима, а состоя- 4.4. ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ АВТОМАТОВ 173 ния Е и Е по входу О переходят в Н и С, соответственно, то пара (Е, Е) также различима.
Фактически, все х на рис. 4.9, за исключением пары (А, б), получаются очень просто; посмотрев на переходы из каждой пары состояний по символам О или 1, обнаружим (для одного из этих символов), что одно состояние переходит в С, а другое — нет. Различимость пары состояний (А, О) видна в следующем цикле, поскольку по символу 1 они переходят в Е и Е, соответственно, а различимость состояний (Е, Е) уже установлена. и А В С Д Е Т 6 Рис.
49. Таблица неэквивалентности состояний Однако обнаружить другие пары различимых состояний невозможно. Следовательно, оставшиеся три пары состояний (А, Е), (В, Н) и (Тл, Е) эквивалентны, Выясним, почему нельзя утверждать, что пара состояний (А, Е) различима. По входному символу О состояния А и Е переходят в В и Н, соответственно, а про эту пару пока неизвестно, различима она, или нет. По символу 1 оба состояния А и Е переходят в Е, так что нет никакой надежды различить нх этим способом. Остальные две пары, (В, Н) и (Р, Е), различить нельзя, поскольку у них одинаковые переходы как по символу О, так и по 1.
Таким образом, алгоритм заполнения таблицы останавливается на таблице, представленной на рис. 4.9, и корректно определяет эквивалентные и различимые состояния. П Теорема 4.20. Если два состояния не различаются с помощью алгоритма заполнения таблицы, то они эквивалентны. Доказательство. Снова рассмотрим ДКА А = Я, Е, б, до, Е). Предположим, что утверждение теоремы неверно, т.е. сушествует хотя бы одна пара состояний (р, 9), для которой выполняются следуюшие условия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
