Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 38
Текст из файла (страница 38)
Для каждого состояния можно вычислить переходы за время 0(и'), используя в-замыкание и таблицу переходов НКА для каждого входного символа. Предположим, нужно вычислить 0((~уп 0л ..., уь), а) для ДКА. Из каждого состояния о, можно достичь не более и состояний вдоль путей с меткой к, и каждое из этих состояний может иметь не более, чем и дуг с меткой а. Создав массив, проиндексироннный состояниями, можно вычислить объединение не более и множеств, состоящих из не более, чем и состояний, за время, пропорциональное и'.
Таким способом для каждого состояния д, можно вычислить множество состояний, достижимых из д, вдоль пути с меткой а (возможно, включая дуги, отмеченные и). Поскольку 1 < и, то существует не более и таких состояний дн и для каждого из них вычис- ' Обсуждение алгоритмоп транзитипного замыкания можно найти в книге А. Ч. АЛо, !. Е. Норсгой, апб Л О. (!Пшап, ГЗаса бииссигех аиИ а18омзйтж АсЫ!зоп-Фез!еу, ! 984. (А. Ахо, Дж.
Хопкрофт, Дж. Уяьман. Структуры данных и алгоритмы, Мг Издательский дом "Вяльямс", 2000,) 4.8. СВОЙСТВА РАЗРЕШИМОСТИ РЕГУЛЯРНЫХ ЯЗЫКОВ 167 ление достижимых состояний занимает время 0(п'). Таким образом, общее время вычисления достижимых состояний равно 0(л'). Для объединения множеств достижимых состояний потребуется только 0(а ) дополнительного времени, следовательно, вычисление одного перехода ДКА занимает время О(и ).
Заметим, что количество входных символов считается постоянным и не зависит от и. Таким образом, как в этой, так и в других оценках времени работы количество входных символов не рассматривается, Размер входного алфавита влияет только на постоянный коэффициент, скрытый в обозначении "О большого". Итак, время преобразования НКА в ДКА, включая ситуацию, когда НКА содержит епереходы, равно 0(а~2"). Конечно, на практике обычно число состояний, которые строятся, намного меньше 2".
Иногда нх всего лишь л. Поэтому можно установить оценку времени работы равной 0(л~з), где я — это число состояний, которые в действительности есть у ДКА. Преобразование ДКА в НКА Это простое преобразование, занилзаюп(ее время О(п) для ДКА с л состояниями. Все, что необходимо сделать, — изменить таблицу переходов для ДКА, заключив в скобки () состояния, а также добавить столбец для я, если нужно получить е-НКА. Поскольку число входных символов (т.е. ширина таблицы переходов) считается постоянным, копирование и обработка таблицы занимает время 0(п). Преобразование автомата в регулярное выражение Рассмотрев конструкцию из раздела 3.2.1, заметим, что на каждом из и этапов (где и — число состояний ДКА) размер конструируемого регулярного выражения может увеличиться в четыре раза, так как каждое выражение строится нз четырех выражений предыдущего цикла.
Таким образом, простая запись и' выражений может занять время 0(п'4"). Улучшенная конструкция из раздела 3.2.2 уменьшает постоянный коэффициент, но не влияет на экспоненциальность этой задачи (в наихудшем случае). Аналогичная консзрукция требует такого же времени работы, если преобразуется НКА, нли даже е-НКА, но зто здесь не доказывается. Однако использование конструкции для НКА имеет большое значение. Если сначала преобразовать НКА в ДКА, а затем ДКА — в регулярное выражение, то на это потребуется время 0(гг'4" ), которое являет- ся дважды экспоненциальным.
Преобразование регулярного выражения в автомат Для преобразования регулярного выражения в е-НКА потребуется линейное время. Необходимо эффективно проанализировать регулярное выражение, используя метод, занимающий время 0(п) для регулярного выражения длины п~. В результате получим де- Методы анализа,'с помощью которых можно выполнить эту задачу за время О(п), обсуждаются в книге А. У. Ано, й. 8е1н(, апб 1. О. ()1!щап, Сотрнег Тзеггяп Ржвс~р(еа Тоо(к апг( Тесящдлек АддЬоп-'1Уез(еу, 1986, (А.
Ахо, Р. Сети, Дж. Ульыан. Комппяяяюры. принципы, инструменты и технологии, М; Издательский доы "Вильямс", 2001.) ГЛАВА 4. СВОЙСТВА РЕГУЛЯРНЫХ ЯЗЫКОВ 168 рево с одним узлом для каждого символа регулярного выражения (хотя скобки в этом дереве не встречаются, поскольку они только управляют разбором выражения). Полученное дерево заданного регулярного выражения можно обработать, конструируя к-НКА для каждого узла.
Правила преобразования регулярного выражения, представленные в разделе 3.2.3, никогда не добавляют более двух состояний и четырех дуг для каждого узла дерева выражения. Следовательно, как число состояний, так и число дуг результирующего к-НКА равны 0(и). Кроме того, работа по созданию этих элементов в каждом узле дерева анализа является постоянной при условии, что функция, обрабатывающая каждое поддерево, возвращает указатели в начальное и допускающие со- стояиня этого автомата. Приходим к выводу, что построение к-НКА по регулярному выражению занимает время, линейно зависящее от размера выражения. Можно исключить к-переходы из к- НКА с и состояниями, преобразовав его в обычный НКА за время 01пз) и не увеличив числа состояний. Однако преобразование в ДКА может занять экспоненциальное время. 4.3.2.
Проверка пустоты регулярных языков На первый взгляд ответ на вопрос "является ли регулярный язык Т. пустым?" кажется очевидным: язык О пуст, а все остальные регулярные языки — нет. Однако, как говорилось в начале раздела4.3, при постановке задачи явный перечень цепочек языка Т. не приводится. Обычно задается некоторое представление языка Т„и нужно решить, обозначает ли оно язык О, или нет. Если язык задан с помощью конечного автомата любого вида, то вопрос пустоты состоит в том, есть ли какие-нибудь пути из начального состояния в допускающие. Если есть, то язык непуст, а если все допускающие состояния изолированы от начального, то язык пуст.
Ответ на вопрос, можно ли перейти в допускающее состояние из начального, является простым примером достижимости в графах, подобным вычислению кямыкання, рассмотренному в разделе 2.5.3. Искомый алгоритм можно сформулировать следующим рекурсивным образом. Базис. Начальное состояние всегда достижимо из начального состояния. Индукции. Если состояние з достижимо из начального, и есть дуга из д в состояние р с любой меткой (входным символом или к, если рассматривается к-НКА), то р также достижимо.
Таким способом можно вычислить все множество достижимых состояний. Если среди них есть допускающее состояние, то ответом на поставленный вопрос будет "нет" (язык данного автомата не пуст), в противном случае ответом будет "да" (язык пуст). Заметим, что если автомат имеет и состояний, то вычисление множества достижимых состояний миимает время не более 0(л~) (практически это время пропорционально числу дуг на диаграмме переходов автомата, которое может быть и меньше и ). г 4.3.
СВОЙСТВА РАЗРЕШИМОСТИ РЕГУЛЯРНЫХ ЯЗЫКОВ 169 Если язык 2, представлен регулярным выражением, а не автоматом, то можно преобразовать это выражение в в-НКА, а далее продолжить так, как описано выше. Поскольку автомат, полученный в результате преобразования регулярного выражения длины л, содержит не более О(п) состояний и переходов, для выполнения алгоритма потребуется время О(п). Можно проверить само выражение — пустое оно, или нет.
Сначала заметим, что если в данном выражении ни разу не встречается О, то его язык гарантированно не пуст. Если же в выражении встречается Я, то язык такого выражения ие обязательно пустой. Ис- пользуя следующие рекурсивные правила, можно определить, представляет ли заданное регулярное выражение пустой язык. Базис. И обозначает пустой язык, но к и а для любого входного символа а обознача- ют не пустой язык. Индукции. Пусть Я вЂ” регулярное выражение. Нужно рассмотреть четыре варианта, соответствующие возможным способам построения этого выражения. 1. Я = Я, ь Яз.
7(Я) пуст тогда и только тогда, когда оба языка ЦЯ~) и А(Я,) пусты. 2. Я = Я~Яд ЦЯ) пуст тогда и только тогда, когда хотя бы один из языков ЦЯ~) и Цяг) пуст. 3. Я = Я,, ЦЯ) не пуст: он содержит цепочку е 4. Я = (Я~), 7(Я) пуст тогда и только тогда, кода ЦЯ,) пуст, так как эти языки равны. 4.3.3. Проверка принадлежности регулярному языку Следующий важный вопрос состоит в том, принадлежит лн данная цепочка н данному регулярному языку 7.. В то время, как цепочка ж задается явно, язык 7.
представляется с помощью автомата или регулярного выражения. Если язык 7. задан с помощью ДКА, то алгоритм решения данной задачи очень прост. Имитируем ДКА, обрабатывающий цепочку входных символов н, начиная со стартового состояния. Если ДКА заканчивает в допускающем состоянии, то цепочка зг принадлежит этому языку, в противном случае — нет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
