Меня интересует классическая проблема РЕГУЛЯРНОГО ВКЛЮЧЕНИЯ ЯЗЫКА. Для регулярного выражения обозначим через L ( E ) связанный с ним регулярный язык. (Регулярные выражения на фиксированном алфавите Σ с объединением операций, звездой Клини и конкатенацией.)
Входные данные: два регулярных выражения и E 2 Вопрос: Верно ли, что L ( E 1 ) ⊆ L ( E 2 ) ?
Известно, что РЕГУЛЯРНОЕ ВКЛЮЧЕНИЕ ЯЗЫКА является PSPACE-полным [1].
Классический способ ее решения (в PSPACE) состоит в том, чтобы создать NFA и A 2, связанные с E 1 и E 2 , построить DFA D 2 из A 2 , дополнить его в DFA D C 2 и, наконец, построить автомат пересечения A P из A 1 и D C 2, соответствующий пересечению L ( E 1 ) и L ( E 2 ) C, Теперь тогда и только тогда, когда в A P нет принимающего пути .
Если я не ошибаюсь, весь процесс может быть выполнен за полиномиальное время, когда является фиксированным языком, поскольку единственное экспоненциальное увеличение происходит от преобразования A 2 в D 2 . Еще лучше проблема заключается в FPT при параметризации | Е 2 | длина Е 2 .
Это мотивирует мой вопрос:
Вопрос: Когда является фиксированным выражением, какова сложность REGULAR LANGUAGE INCLUSION? Это остается PSPACE-полным?
[1] Л.Дж. Стокмейер и А.Р. Мейер. Проблемы со словами, требующие экспоненциального времени: предварительный отчет. Материалы пятого ежегодного симпозиума ACM по теории вычислений, STOC '73, стр. 1-9.
Замечание: будучи не экспертом в этой области, я нахожу [1] (и связанные с ним статьи того времени) совершенно нечитабельным и не смог найти другого доказательства полноты PSPACE - любого указателя на современное доказательство, такого как в книга, очень приветствуется! Кроме того, авторы, кажется, допускают возведение в квадрат в своих регулярных выражениях, что, на мой взгляд, в настоящее время довольно нестандартно.)
Ответы:
Частный случай универсальности языка (все ли слова приняты?) Является PSPACE-полным для регулярных выражений или NFA. Он отвечает на ваш вопрос: в общем случае задача остается PSPACE-полной даже для фиксированного , поскольку универсальность языка соответствует E 1 = Σ ∗ .Е1 Е1= Σ*
Действительно трудно найти современное удобочитаемое доказательство твердости PSPACE для универсальности регулярных выражений, поскольку теперь это считается фольклором. Вот схема быстрого доказательства, которая позволяет перестроить доказательство:
Рассмотрим машину Тьюринга на алфавите Е с использованием полиномиального пространства р ( п ) , и пусть W ∈ Е * входное слово для M . Мы построим регулярное выражение e, которое принимает все слова в том и только в том случае, если M не принимает прогон на w .M Σ p ( n ) w ∈ Σ* M е M вес
Рассмотрим язык состоящий из слов вида $ C 0 $ C 1 $ … $ C f $ , где каждый C i является конфигурацией M длины ровно p ( n ) , C 0 является начальной конфигурацией с w на лента, С F принимает, и каждый из С я → С я + 1 является допустимым переход М . Слово в LLM $ C0$ C1$ … $ Cе$ Ся M p ( n ) С0 вес Се Ся→ Cя + 1 M описывает принимающую пробег M .LM M
Мы строим на алфавите Х ' = Е ∪ { $ } такие , что е принимает именно те слова, которые не в L M , посмотрев за нарушение определения L M . Выражение e будет большой дизъюнкцией e 1 + e 2 + ⋯ + e k , где каждый e i ищет различный вид нарушения. Например, e 1 = ( Σ ′ ) ∗ $е Σ'= Σ ∪ { $ } е LM LM е е1+ е2+ ⋯ + eК ея ищет нарушение того факта, что каждый C i имеет размер ровно p ( n ) . Самая сложная часть - угадать нарушение между C i и C i + 1 : выражение может сравнивать локальный шаблон в C i и его изображение в C i + 1 , используя t
Конечно, как отметил Майкл Вехар в комментариях, для других проблема может стать проще. Классификация сложности этой проблемы широко изучалась в этой статье [1] на предмет эквивалентности, локализации и покрытия. Вы можете увидеть сводку результатов для проблемы эквивалентности в этом ответе (существуют NP-полные случаи).Е1
[1] Об эквивалентности, содержании и проблемах покрытия для регулярных и контекстно-свободных языков Гарри Б. Хант, Даниэль Дж. Розенкранц, Томас Г. Шимански. Журнал компьютерных и системных наук. Том 12, выпуск 2, апрель 1976 года, страницы 222-268
[2] Проблема эквивалентности для регулярных выражений с возведением в квадрат требует экспоненциального пространства . Мейер, AR и Л. Стокмейер. 13-й симпозиум IEEE по теории коммутации и автоматов, октябрь 1972 г., с. 125–129.
источник