Вопросы с тегом «regular-expressions»

Вопросы по теории регулярных выражений, как в смысле оригинального определения Клини, так и в смысле регулярных выражений POSIX.

43
Является ли нахождение минимального регулярного выражения NP-полной проблемой?

Я думаю о следующей проблеме: я хочу найти регулярное выражение, которое соответствует определенному набору строк (например, действительные адреса электронной почты) и не соответствует другим (недействительные адреса электронной почты). Предположим, что под регулярным выражением мы подразумеваем...

36
Регулярные выражения не

Спросите даже кого-то, имеющего опыт работы в области компьютерных наук, что такое регулярное выражение, и ответ, вероятно, выйдет за пределы возможности быть в пределах досягаемости конечного автомата. Например, «регулярное выражение» /^1?$|^(11+?)\1+$/ созданная известной личностью Perl Абигейл...

30
Есть ли «маленькие» машины, которые могут эффективно сопоставлять регулярные выражения?

Хорошо известно, что регулярное выражение может быть распознано недетерминированным конечным автоматом, размер которого пропорционален регулярному выражению, или детерминированным FA, который потенциально экспоненциально больше. Кроме того, учитывая строку и регулярное выражение , NFA может...

28
Известные алгоритмы перехода от DFA к регулярному выражению

Мне было интересно, существует ли «лучший» (я объясню в каком смысле) алгоритм для запуска из DFA и построения регулярного выражения такого что , чем в книге Хопкрофта и Уллмана (1979). Там наборы используются для представления наборов строк, которые переводят DFA из состояния в без прохождения...

27
Почему обычные языки называются «обычными»?

Почему регулярные языки (и из этих регулярных выражений) называются "регулярными"? Существует много закономерностей и в контекстно-свободных языках других типов языков. Я предполагаю, что в начале прилагательное «обычный» использовалось для того, чтобы отличать этот тип языков от других...

22
Номер раздела протокола и детерминированная сложность связи

Помимо (детерминированной) сложности связи отношения , другой основной мерой для объема необходимой связи является номер раздела протокола . Связь между этими двумя показателями известна до постоянного фактора. Монография Кушилевица и Нисана (1997) даетRc c ( R )сс(р)cc(R)ррR p p ( R )пп(р)pp(R) c...

21
Для каких регулярных выражений

Хорошо известно, что следующая проблема является PSPACE-полной: Учитывая регулярное выражение , ?L ( β ) = Σ ∗ββ\betaL ( β) = Σ*L(β)=Σ∗L(\beta) = \Sigma^* Как насчет определения эквивалентности другим (фиксированным) регулярным выражениям ?αα\alpha Учитывая регулярное выражение , ?L ( β ) = L ( α...

19
Где большинство реализаций REGEX попадают в шкалу сложности?

Большинство современных реализаций регулярных выражений, таких как perl или .NET, выходят за рамки классического компьютерного определения REGEX с такими функциями, как lookahead и lookbehind. Позволяют ли эти функции анализировать операторы, которые не могут быть описаны конечным автоматом без...

19
Является ли JSON обычным языком?

Мне было интересно, если спецификация JSON определяет обычный язык. Это кажется достаточно простым, но я не уверен, как это доказать самому. Причина, по которой я спрашиваю, заключается в том, что мне было интересно, можно ли использовать регулярные выражения для эффективного анализа JSON. Может ли...

16
Можно ли недетерминированные конечные автоматы (NDFA) эффективно преобразовать в детерминированные конечные автоматы (DFA) в субэкспоненциальном пространстве / времени?

Двадцать лет назад я создал пакет регулярных выражений, который включал преобразования из регулярных выражений в конечный автомат (DFA) и поддерживал множество закрытых операций с регулярными выражениями (звезда Клина, конкатенация, обратное, операции над множествами и т. Д.). Я не был уверен в...

15
Прогресс в обобщенной проблеме звездной высоты?

(Обобщенная) высота звезды в языке - это минимальная вложенность звезд Клини, необходимая для представления языка расширенным регулярным выражением. Напомним, что расширенное регулярное выражение над конечным алфавитом удовлетворяет следующему:AAA (1) и - расширенные регулярные выражения для...

15
минимизация размера регулярного выражения для конечных множеств

Известно, что минимизация размера регулярного выражения является PSPACE-полной, даже если у нас есть DFA в качестве спецификации языка . Каковы результаты, если язык конечен? Можно рассмотреть эту проблему в двух моделях: Входные данные - это все строки в языке, и мы измеряем размер ввода как сумму...

14
Иерархии на обычных языках

Существует ли какая-либо известная «хорошая» иерархия L0⊆L1⊆L2⊆…L0⊆L1⊆L2⊆…L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots (может быть конечной) внутри класса регулярных языков ? К счастью, классы в каждой иерархии отражают различную выразительность / мощность / сложность. Кроме того, членство...

12
Стоимость запроса эквивалентности для DFA

Вдохновленный этим вопросом , мне интересно следующее: Какова сложность наихудшего случая проверки, принимает ли данный DFA тот же язык, что и данное регулярное выражение? Это известно? Надежда будет заключаться в том, что эта проблема в P - что есть алгоритм полинома в размере...

11
Параметризованная сложность включения обычных языков

Меня интересует классическая проблема РЕГУЛЯРНОГО ВКЛЮЧЕНИЯ ЯЗЫКА. Для регулярного выражения обозначим через L ( E ) связанный с ним регулярный язык. (Регулярные выражения на фиксированном алфавите Σ с объединением операций, звездой Клини и конкатенацией.)ЕЕEL ( E)L(Е)L(E)ΣΣ\Sigma Входные данные:...

11
Какие существуют алгоритмы для построения DFA, который распознает язык, описанный данным регулярным выражением?

Все мои учебники используют один и тот же алгоритм для создания DFA с заданным регулярным выражением: во-первых, создайте NFA, который распознает язык регулярных выражений, затем, используя конструкцию подмножества (он же «powerset»), преобразуйте NFA в эквивалентный DFA ( при желании...

10
Таксономия известных автоматов регулярных выражений

Я пытаюсь составить таксономию алгоритмов для преобразования регулярных выражений в автоматы, чтобы выполнить некоторые эмпирические тесты их свойств сложности в определенных областях. Я знаю несколько «больших» имен, например: Томпсон «Алгоритм поиска регулярных выражений», Томпсон, 1968 Глушков...

9
Регулярные выражения без чередования

Мне было интересно, какие наборы языков генерируются ограничениями регулярных выражений. Предположим, что все ограничения имеют постоянный символ для каждого элемента и конкатенации. Тогда восемь классов могут быть сформированы наличием или отсутствием дополнения / отрицания, изменения /...