Почему в регулярных выражениях нет перестановок? (Даже если обычные языки, кажется, могут это сделать)

13

Проблема

Нет простого способа получить перестановку с помощью регулярного выражения.

  • Перестановка: Получение слово ( «ААБК») в другом порядке, без изменения числа или рода писем.
    w=x1xn
  • Regex: Регулярное выражение.

Для подтверждения:

Тип решения, которое я ищу

Должен иметь форму:

  • »Aabc« (или все, что вы могли бы использовать открывающие и закрывающие скобки)
  • (AABC)! (аналогично (abc)? но с другим символом в конце)
  • [AABC]! (аналогично [abc] +, но с другим символом в конце)

Преимущества этих решений

Они есть:

  • легко
  • адаптируются
  • многоразовый

Почему это должно существовать

  • Регулярные выражения - это способ описания грамматики обычного языка. У них есть полная возможность быть любым обычным языком.
  • Скажем, обычные языки достаточно мощны для перестановок (доказательство ниже) - почему нет простого способа выразить это?

Итак, мой вопрос:

  • (Почему) Мое доказательство неверно?
  • Если это правильно: почему нет простого способа выразить перестановки?

Доказательство

  • Регулярные выражения являются одним из способов отметить грамматику обычного языка. Они могут описать любую грамматику обычных языков.
  • Еще один способ описать грамматику любых обычных языков (которые имеют конечное число букв в алфавите) - это недетерминированные автоматы (с конечным числом состояний).

Имея конечное количество букв, я могу создать этот автомат: (Пример. Формально: см. Ниже)

Грамматика, которая принимает перестановки "abbc":

(извините за числа сверху, может кто-то знает, как сделать эту часть лучше)

s -> ах

s -> чч

с -> ч³

h¹ -> bh¹¹

ч¹ -> ч¹²

h² -> ах¹¹ (нет опечатки! эквивалентность)

h² -> bh²²

ч² -> ч²³

ч³ -> ах¹²

ч³ -> чч³

ч¹¹ -> до н.э

h¹¹ -> cb

h¹² -> бб

h²² -> ac

h²² -> ca

h²³ -> ab

ч²³ -> ба

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

  • Слово q (с конечной длиной), которому любая перестановка должна достичь принимающего состояния.
  • Х это конечный алфавит.
  • Набор состояний S содержит любой порядок букв вплоть до длины q. (Таким образом, размер S конечен.) Плюс одно состояние «больше слова».
  • функция перехода состояния d, которая принимает букву и перемещается в состояние, соответствующее прочитанной части слова.
  • F - это множество состояний, которые являются точными перестановками q.

Таким образом, можно создать автомат конечного состояния для принятия перестановок данного слова.

Идем дальше с доказательством

Итак, я доказал, что обычные языки способны проверять перестановки, не так ли?

Так почему нет подходов для достижения этого с помощью регулярных выражений? Это полезный функционал.

Asqiir
источник
10
Вы можете перечислить все перестановки вашего слова с помощью регулярного выражения. Полученное выражение будет довольно большим, но определенно будет регулярным выражением.
Юваль Фильмус
7
Я предлагаю игнорировать все ответы о теории вычислений на stackoverflow. Это не специальность этого сайта.
Юваль Фильмус
Ответ на вашей связанной странице здесь - stackoverflow.com/a/3102205/6936386 - кажется легко адаптируемым и не слишком сложным: ^(a()|a()|b()|c()){4}\2\3\4\5$кажется, работает (см. Regex101.com/r/9URPpg/4/tests ).
boboquack
7
@boboquack Это не регулярное выражение в том смысле, в котором этот термин используется в информатике. (Именно из-за этого Ювал предлагает не доверять ответам Stack Overflow о теоретической CS.)
Дэвид Ричерби

Ответы:

37

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

Предположу , мы добавим новое правило для создания регулярных выражений: если  является регулярным выражением, то является регулярным выражением, и она соответствует каждой перестановке каждой строки , совпавших  . Так, например, . Проблема в том, что это нарушает фундаментальные эквивалентности, описанные выше. - это язык строк, которые содержат одинаковое число и s, и это не обычный язык. Сравните это, например, с добавлением оператора отрицания или обращения к регулярным выражениям, который не меняет класс языков, которые принимаются.Rπ(R)RL(π(abc))={abc,acb,bac,bca,cab,cba}L(π((ab))))ab

Итак, чтобы ответить на заглавный вопрос, регулярные выражения не могут выполнять перестановки, и мы не добавляем эту возможность, потому что тогда регулярные выражения не будут соответствовать регулярным языкам. Сказав это, возможно, что «регулярные выражения с перестановками» также будут интересным классом языков с множеством различных характеристик.

Дэвид Ричерби
источник
Но L ((ab) *) также не является обычным языком - поэтому L (perm ((ab) *)) не может быть одним. ((ab) * не является обычным языком, так как нет никакой памяти, чтобы помнить, сколько существует открывающих «a», поэтому с конечным числом состояний вы не можете поместить одинаковое количество «b» s.)
Asqiir
9
@Asqiir является регулярным, потому что это язык, которому соответствует данное регулярное выражение. Вы, кажется, неправильно поняли, что это за язык. Это , а не . Последний язык не является обычным, но это не тот язык, о котором мы говорим. L((ab)){ε,ab,abab,ababab,abababab,}{ε,ab,aabb,aaabbb,aaaabbbb,}
Дэвид Ричерби
4
@Asqiir Это тот язык, потому что это то, что вы получаете, применяя любую перестановку, которую хотите, к языку, в котором каждая строка содержит одинаковое число и s; это не регулярно, потому что вы можете доказать это, используя лемму прокачки. ab
Дэвид Ричерби
2
Вы совершенно правы. Я упустил смысл «помещать регулярные выражения друг в друга», я думал только о «перестановке фиксированного слова», а не «перестановке другого регулярного выражения», что, конечно, невозможно.
Asqiir
1
Возможно, регулярные выражения с перестановками описывают класс языков с интересными свойствами, но я никогда не сталкивался с необходимостью в !операторе на практике, и я полагаю, что мало людей, поскольку это легко реализовать, и нет реализации расширенных регулярных выражений. Видел, поддерживает это.
reinierpost
16

Итак, мой вопрос:

  • (Почему) Мое доказательство неверно?
  • Если это правильно: почему нет простого способа выразить перестановки?

Ваше «доказательство» смотрело только на перестановки отдельных слов, которые являются конечными языками.

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

Как только вы получаете регулярное выражение (или грамматику / автомат), которое принимает бесконечный язык (т.е. выражение с *оператором, или автомат с циклом), ваша конструкция больше не работает (вы получаете бесконечную грамматику / автомат ).

Ответ Дэвида Ричерби привел пример обычного языка, язык перестановок которого больше не является регулярным - все такие примеры являются бесконечными языками.

Пауло Эберманн
источник
8

Пусть будет алфавитом размера . Регулярное выражение, описывающее все перестановки должно иметь экспоненциальный размер. Это следует из теоремы 9 в « Нижние оценки для контекстно-свободных грамматик» , которая дает экспоненциальную нижнюю оценку гораздо более сильной модели контекстно-свободных грамматик (регулярное выражение размера можно преобразовать в контекстную грамматику размера ).ΣnΣmO(m)

Так что в некотором смысле нет краткого способа указать все перестановки слова.


Вот простое доказательство нижней оценки на размер регулярного выражения для языка всех перестановок алфавита размера . Поскольку регулярное выражение размера можно преобразовать в NFA с состояниями , достаточно дать нижнюю границу для NFA.Ω~(2n)ΣnmO(m)

Мы будем использовать метод набора дурака , который мы сейчас опишем. Пусть - язык, и пусть - набор пар слов, таких что:L(xi,yi)1iN

  • xiyiL .
  • Если , то либо или .ijxiyjLxjyiL

Тогда каждый NFA для содержит хотя бы состояний. Действительно, рассмотрим любой НКА для . Для каждого рассмотрим некоторые принимающие вычисления , и пусть будет состоянием, в котором находится NFA после чтения в этом принимающем вычислении. Я утверждаю, что для . Действительно, если то «вырезать и вставить» показывает, что и находятся в , вопреки предположению.LNLixiyiqixiqiqjijqi=qjxiyjxjyiL

Теперь мы можем доказать нижнюю оценку NFA для языка всех перестановок символов ; для простоты изложения мы предполагаем, что четно. Для каждого подмножества из размера , пусть состоит из всех символов в в некотором произвольном порядке, а состоит из всех символов не в в некотором произвольном порядке. Ясно, что . И наоборот, если то . Это показывает, что каждый NFA дляLnσ1,,σnnSσ1,,σnn/2xSSySSxSySLnSTxSyTLnLnсодержит как минимум много состояний.(nn/2)=Ω(2n/n)

Юваль Фильмус
источник
Означает ли это, что 1) теоретически можно было бы позволить »abc« соответствовать всем {abc, acb, bac, bca, cab, cba}, но это просто неэффективно и сделает их слишком медленными, поскольку »abc« будет экспоненциально расширяться до (а | ACB | BAC | BCA | кабина | сЬы)? или 2) тот тип автомата, который мне нужен, не может указать все перестановки для данного слова?
Asqiir
1
Вот регулярное выражение, которое соответствует всем перестановкам : . Вы можете легко преобразовать это в DFA, имеющий состояний. То же самое работает для . a b c + a c d + b a c + b c a + c a b + c b a 1 + 3 + 6 + 6 + 1 = 17 a b c d e f g h i jabcabc+acd+bac+bca+cab+cba1+3+6+6+1=17abcdefghij
Юваль Фильмус
1
Что я понял: в теории регулярные языки могут принимать перестановки (как и регулярные выражения). Нет просто «простого способа» написать «перестановка abc», как »abc«. (По каким-либо причинам.)
Asqiir
1
Да, это хорошее резюме. Я посмотрю, смогу ли я придумать более простой аргумент для регулярных выражений.
Юваль Фильмус
2
Для будущих читателей: это не правильный ответ! (Поправьте меня, если я ошибаюсь.) Ищите принятый.
Asqiir
0

Почему нет способа написать «перестановка» в регулярных выражениях

Перестановка регулярного, бесконечного языка (бесконечного количества слов) не обязательно регулярна. Таким образом, это не может быть записано как регулярное выражение.

доказательство

Подумайте о языке (ab)*. (Пример вдохновлен Дэвидом Ричерби .) Одна из его перестановок - a*b*. Это не обычный язык. ч.т.д..

Asqiir
источник