Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
курсс.docx
Скачиваний:
0
Добавлен:
01.07.2025
Размер:
244 Кб
Скачать
☆

Преобразование дка в нка

Это простое преобразование, занимающее время O(n) для ДКА с n состояниями. Все, что необходимо сделать, — изменить таблицу переходов для ДКА, заключив в скобки {} состояния, а также добавить столбец для ε, если нужно получить ε-НКА. Поскольку число входных символов (т.е. ширина таблицы переходов) считается постоянным, копирование и обработка таблицы занимает время O(n).

Преобразование автомата в регулярное выражение

Каждом из n этапов (где n — число состояний ДКА) размер конструируемого регулярного выражения может увеличиться в четыре раза, так как каждое выражение строится из четырех выражений предыдущего цикла. Таким образом, простая запись n3 выражений может занять время O(n34n). Улучшенная конструкция из раздела 3.2.2 уменьшает постоянный коэффициент, но не влияет на экспоненциальность этой задачи (в наихудшем случае).

Аналогичная конструкция требует такого же времени работы, если преобразуется НКА, или даже ε-НКА, но это здесь не доказывается. Однако использование конструкции для НКА имеет большое значение. Если сначала преобразовать НКА в ДКА, а затем ДКА — в регулярное выражение, то на это потребуется время O(n34n32n), которое является дважды экспоненциальным.

Преобразование регулярного выражения в автомат

Для преобразования регулярного выражения в ε-НКА потребуется линейное время. Необходимо эффективно проанализировать регулярное выражение, используя метод, занимающий время O(n) для регулярного выражения длины n6. В результате получим дерево с одним узлом для каждого символа регулярного выражения (хотя скобки в этом дереве не встречаются, поскольку они только управляют разбором выражения).

Полученное дерево заданного регулярного выражения можно обработать, конструируя ε-НКА для каждого узла. Правила преобразования регулярного выражения, представленные в разделе 3.2.3, никогда не добавляют более двух состояний и четырех дуг для каждого узла дерева выражения. Следовательно, как число состояний, так и число дуг результирующего ε-НКА равны O(n). Кроме того, работа по созданию этих элементов в каждом узле дерева анализа является постоянной при условии, что функция, обрабатывающая каждое поддерево, возвращает указатели в начальное и допускающие состояния этого автомата.

Приходим к выводу, что построение ε-НКА по регулярному выражению занимает время, линейно зависящее от размера выражения. Можно исключить ε-переходы из ε- НКА с n состояниями, преобразовав его в обычный НКА за время O(n3) и не увеличив числа состояний. Однако преобразование в ДКА может занять экспоненциальное время.

Проверка пустоты регулярных языков

На первый взгляд ответ на вопрос “является ли регулярный язык L пустым?” кажется очевидным: язык ∅ пуст, а все остальные регулярные языки — нет. Однако, как говорилось в начале раздела 4.3, при постановке задачи явный перечень цепочек языка L не приводится. Обычно задается некоторое представление языка L, и нужно решить, обозначает ли оно язык ∅, или нет.

Если язык задан с помощью конечного автомата любого вида, то вопрос пустоты состоит в том, есть ли какие-нибудь пути из начального состояния в допускающие. Если есть, то язык непуст, а если все допускающие состояния изолированы от начального, то язык пуст. Ответ на вопрос, можно ли перейти в допускающее состояние из начального, является простым примером достижимости в графах, подобным вычислению ε-замыкания, рассмотренному в разделе 2.5.3. Искомый алгоритм можно сформулировать следующим рекурсивным образом.

Базис. Начальное состояние всегда достижимо из начального состояния.

Индукция. Если состояние q достижимо из начального, и есть дуга из q в состояние p с любой меткой (входным символом или ε, если рассматривается ε-НКА), то p также достижимо.

Таким способом можно вычислить все множество достижимых состояний. Если среди них есть допускающее состояние, то ответом на поставленный вопрос будет “нет” (язык данного автомата не пуст), в противном случае ответом будет “да” (язык пуст). Заметим, что если автомат имеет n состояний, то вычисление множества достижимых состояний занимает время не более O(n2) (практически это время пропорционально числу дуг на диаграмме переходов автомата, которое может быть и меньше n2).

Если язык 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) пуст, так как эти языки равны.