Свойства регулярных языков (1134638), страница 7
Текст из файла (страница 7)
Основное влияние на расход времени оказывает количество состоянийДКА, которое может равняться 2n. Для каждого состояния можно вычислить переходы завремя O(n3), используя ε-замыкание и таблицу переходов НКА для каждого входногосимвола. Предположим, нужно вычислить δ({q1, q2, …, qk}, a) для ДКА. Из каждого состояния qi можно достичь не более n состояний вдоль путей с меткой ε, и каждое из этихсостояний может иметь не более, чем n дуг с меткой a. Создав массив, проиндексированный состояниями, можно вычислить объединение не более n множеств, состоящих изне более, чем n состояний, за время, пропорциональное n2.Таким способом для каждого состояния qi можно вычислить множество состояний,достижимых из qi вдоль пути с меткой a (возможно, включая дуги, отмеченные ε).
Поскольку k ≤ n, то существует не более n таких состояний qi, и для каждого из них вычис5Обсуждение алгоритмов транзитивного замыкания можно найти в книге A. V. Aho,J. E. Hopcroft, and J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, 1984. (А. Ахо,Дж. Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы, М.: Издательский дом“Вильямс”, 2000.)4.3.
ÑÂÎÉÑÒÂÀ ÐÀÇÐÅØÈÌÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ167ление достижимых состояний занимает время O(n2). Таким образом, общее время вычисления достижимых состояний равно O(n3). Для объединения множеств достижимыхсостояний потребуется только O(n2) дополнительного времени, следовательно, вычисление одного перехода ДКА занимает время O(n3).Заметим, что количество входных символов считается постоянным и не зависит от n.Таким образом, как в этой, так и в других оценках времени работы количество входныхсимволов не рассматривается.
Размер входного алфавита влияет только на постоянныйкоэффициент, скрытый в обозначении “О большого”.Итак, время преобразования НКА в ДКА, включая ситуацию, когда НКА содержит εпереходы, равно O(n32n). Конечно, на практике обычно число состояний, которые строятся,намного меньше 2n. Иногда их всего лишь n. Поэтому можно установить оценку времени работы равной O(n3s), где s — это число состояний, которые в действительности есть у ДКА.Преобразование ДКА в НКАЭто простое преобразование, занимающее время O(n) для ДКА с n состояниями.
Все,что необходимо сделать, — изменить таблицу переходов для ДКА, заключив в скобки {}состояния, а также добавить столбец для ε, если нужно получить ε-НКА. Поскольку число входных символов (т.е. ширина таблицы переходов) считается постоянным, копирование и обработка таблицы занимает время O(n).Преобразование автомата в регулярное выражениеРассмотрев конструкцию из раздела 3.2.1, заметим, что на каждом из n этапов (гдеn — число состояний ДКА) размер конструируемого регулярного выражения может увеличиться в четыре раза, так как каждое выражение строится из четырех выражений предыдущего цикла. Таким образом, простая запись n3 выражений может занять времяO(n34n).
Улучшенная конструкция из раздела 3.2.2 уменьшает постоянный коэффициент,но не влияет на экспоненциальность этой задачи (в наихудшем случае).Аналогичная конструкция требует такого же времени работы, если преобразуетсяНКА, или даже ε-НКА, но это здесь не доказывается. Однако использование конструкциидля НКА имеет большое значение. Если сначала преобразовать НКА в ДКА, а затем3 nДКА — в регулярное выражение, то на это потребуется время O(n34n 2 ), которое является дважды экспоненциальным.Преобразование регулярного выражения в автоматДля преобразования регулярного выражения в ε-НКА потребуется линейное время.Необходимо эффективно проанализировать регулярное выражение, используя метод, занимающий время O(n) для регулярного выражения длины n6.
В результате получим де-6Методы анализа, с помощью которых можно выполнить эту задачу за время O(n), обсуждаются в книге A. V. Aho, R. Sethi, and J. D. Ullman, Compiler Design: Principles, Tools, andTechniques, Addison-Wesley, 1986. (А. Ахо, Р. Сети, Дж. Ульман. Компиляторы: принципы, инструменты и технологии, М.: Издательский дом “Вильямс”, 2001.)168ÃËÀÂÀ 4. ÑÂÎÉÑÒÂÀ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂрево с одним узлом для каждого символа регулярного выражения (хотя скобки в этомдереве не встречаются, поскольку они только управляют разбором выражения).Полученное дерево заданного регулярного выражения можно обработать, конструируя ε-НКА для каждого узла.
Правила преобразования регулярного выражения, представленные в разделе 3.2.3, никогда не добавляют более двух состояний и четырех дугдля каждого узла дерева выражения. Следовательно, как число состояний, так и числодуг результирующего ε-НКА равны O(n). Кроме того, работа по созданию этих элементов в каждом узле дерева анализа является постоянной при условии, что функция, обрабатывающая каждое поддерево, возвращает указатели в начальное и допускающие состояния этого автомата.Приходим к выводу, что построение ε-НКА по регулярному выражению занимаетвремя, линейно зависящее от размера выражения.
Можно исключить ε-переходы из εНКА с n состояниями, преобразовав его в обычный НКА за время O(n3) и не увеличивчисла состояний. Однако преобразование в ДКА может занять экспоненциальное время.4.3.2. Ïðîâåðêà ïóñòîòû ðåãóëÿðíûõ ÿçûêîâНа первый взгляд ответ на вопрос “является ли регулярный язык L пустым?” кажетсяочевидным: язык ∅ пуст, а все остальные регулярные языки — нет. Однако, как говорилось в начале раздела 4.3, при постановке задачи явный перечень цепочек языка L неприводится. Обычно задается некоторое представление языка L, и нужно решить, обозначает ли оно язык ∅, или нет.Если язык задан с помощью конечного автомата любого вида, то вопрос пустоты состоит в том, есть ли какие-нибудь пути из начального состояния в допускающие.
Еслиесть, то язык непуст, а если все допускающие состояния изолированы от начального, тоязык пуст. Ответ на вопрос, можно ли перейти в допускающее состояние из начального,является простым примером достижимости в графах, подобным вычислению εзамыкания, рассмотренному в разделе 2.5.3. Искомый алгоритм можно сформулироватьследующим рекурсивным образом.Базис. Начальное состояние всегда достижимо из начального состояния.Индукция. Если состояние q достижимо из начального, и есть дуга из q в состояние pс любой меткой (входным символом или ε, если рассматривается ε-НКА), то p такжедостижимо.Таким способом можно вычислить все множество достижимых состояний.
Если срединих есть допускающее состояние, то ответом на поставленный вопрос будет “нет” (языкданного автомата не пуст), в противном случае ответом будет “да” (язык пуст). Заметим,что если автомат имеет n состояний, то вычисление множества достижимых состоянийзанимает время не более O(n2) (практически это время пропорционально числу дуг надиаграмме переходов автомата, которое может быть и меньше n2).4.3. ÑÂÎÉÑÒÂÀ ÐÀÇÐÅØÈÌÎÑÒÈ ÐÅÃÓËßÐÍÛÕ ßÇÛÊÎÂ169Если язык L представлен регулярным выражением, а не автоматом, то можно преобразовать это выражение в ε-НКА, а далее продолжить так, как описано выше. Посколькуавтомат, полученный в результате преобразования регулярного выражения длины n, содержит не более O(n) состояний и переходов, для выполнения алгоритма потребуетсявремя O(n).Можно проверить само выражение — пустое оно, или нет. Сначала заметим, что еслив данном выражении ни разу не встречается ∅, то его язык гарантированно не пуст.
Еслиже в выражении встречается ∅, то язык такого выражения не обязательно пустой. Используя следующие рекурсивные правила, можно определить, представляет ли заданноерегулярное выражение пустой язык.Базис. ∅ обозначает пустой язык, но ε и a для любого входного символа a обозначают не пустой язык.Индукция. Пусть R — регулярное выражение.
Нужно рассмотреть четыре варианта,соответствующие возможным способам построения этого выражения.1.R = R1 + R2. L(R) пуст тогда и только тогда, когда оба языка L(R1) и L(R2) пусты.2.R = R1R2. L(R) пуст тогда и только тогда, когда хотя бы один из языков L(R1) иL(R2) пуст.3.R = R1*. L(R) не пуст: он содержит цепочку ε.4.R = (R1). L(R) пуст тогда и только тогда, кода L(R1) пуст, так как эти языки равны.4.3.3. Ïðîâåðêà ïðèíàäëåæíîñòè ðåãóëÿðíîìó ÿçûêóСледующий важный вопрос состоит в том, принадлежит ли данная цепочка w данному регулярному языку L.
В то время, как цепочка w задается явно, язык L представляетсяс помощью автомата или регулярного выражения.Если язык L задан с помощью ДКА, то алгоритм решения данной задачи очень прост.Имитируем ДКА, обрабатывающий цепочку входных символов w, начиная со стартовогосостояния. Если ДКА заканчивает в допускающем состоянии, то цепочка w принадлежитэтому языку, в противном случае — нет. Этот алгоритм является предельно быстрым.Если |w| = n и ДКА представлен с помощью подходящей структуры данных, например,двухмерного массива (таблицы переходов), то каждый переход требует постоянноговремени, а вся проверка занимает время O(n).Если L представлен способом, отличным от ДКА, то преобразуем это представление вДКА и применим описанную выше проверку.
Такой подход может занять время, экспоненциально зависящее от размера данного представления и линейное относительно |w|.Однако, если язык задан с помощью НКА или ε-НКА, то намного проще и эффективнеенепосредственно проимитировать этот НКА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
