Проблема
Нет простого способа получить перестановку с помощью регулярного выражения.
- Перестановка: Получение слово ( «ААБК») в другом порядке, без изменения числа или рода писем.
- Regex: Регулярное выражение.
Для подтверждения:
- «Перестановки регулярных выражений без повторения» Ответ создает код JavaScript вместо регулярного выражения, предполагая, что это будет более простым.
- «Как найти все перестановки данного слова в данном тексте» - в ответе также не используются регулярные выражения.
- «Regex для соответствия всем {1, 2, 3, 4} без повторений» - в ответе используются регулярные выражения, но он не является ни адаптивным, ни простым.
- Этот ответ даже утверждает: «Регулярное выражение не может делать то, что вы просите. Оно не может генерировать перестановки из строки» .
Тип решения, которое я ищу
Должен иметь форму:
- »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.
Таким образом, можно создать автомат конечного состояния для принятия перестановок данного слова.
Идем дальше с доказательством
Итак, я доказал, что обычные языки способны проверять перестановки, не так ли?
Так почему нет подходов для достижения этого с помощью регулярных выражений? Это полезный функционал.
^(a()|a()|b()|c()){4}\2\3\4\5$
кажется, работает (см. Regex101.com/r/9URPpg/4/tests ).Ответы:
Фундаментальные теоремы теории формального языка заключаются в том, что регулярные выражения, регулярные грамматики, детерминированные конечные автоматы (DFA) и недетерминированные конечные автоматы (NFA) описывают одни и те же типы языков: а именно регулярные языки. Тот факт, что мы можем описать эти языки очень разными способами, говорит о том, что в этих языках есть что-то естественное и важное, точно так же, как эквивалентность машин Тьюринга, лямбда-исчисления и всех других вещей предполагает, что вычислимые языки естественны и важны. Они не просто артефакт любых случайных решений, которые принял первоначальный исследователь.
Предположу , мы добавим новое правило для создания регулярных выражений: если является регулярным выражением, то является регулярным выражением, и она соответствует каждой перестановке каждой строки , совпавших . Так, например, . Проблема в том, что это нарушает фундаментальные эквивалентности, описанные выше. - это язык строк, которые содержат одинаковое число и s, и это не обычный язык. Сравните это, например, с добавлением оператора отрицания или обращения к регулярным выражениям, который не меняет класс языков, которые принимаются.R π(R) R L(π(abc))={abc,acb,bac,bca,cab,cba} L(π((ab)∗))) a b
Итак, чтобы ответить на заглавный вопрос, регулярные выражения не могут выполнять перестановки, и мы не добавляем эту возможность, потому что тогда регулярные выражения не будут соответствовать регулярным языкам. Сказав это, возможно, что «регулярные выражения с перестановками» также будут интересным классом языков с множеством различных характеристик.
источник
!
операторе на практике, и я полагаю, что мало людей, поскольку это легко реализовать, и нет реализации расширенных регулярных выражений. Видел, поддерживает это.Ваше «доказательство» смотрело только на перестановки отдельных слов, которые являются конечными языками.
Каждый конечный язык является регулярным (например, просто перечисляя всех членов с
|
промежуточным звеном), но существуют бесконечные регулярные языки (и, как правило, они являются наиболее интересными).Как только вы получаете регулярное выражение (или грамматику / автомат), которое принимает бесконечный язык (т.е. выражение с
*
оператором, или автомат с циклом), ваша конструкция больше не работает (вы получаете бесконечную грамматику / автомат ).Ответ Дэвида Ричерби привел пример обычного языка, язык перестановок которого больше не является регулярным - все такие примеры являются бесконечными языками.
источник
Пусть будет алфавитом размера . Регулярное выражение, описывающее все перестановки должно иметь экспоненциальный размер. Это следует из теоремы 9 в « Нижние оценки для контекстно-свободных грамматик» , которая дает экспоненциальную нижнюю оценку гораздо более сильной модели контекстно-свободных грамматик (регулярное выражение размера можно преобразовать в контекстную грамматику размера ).Σ n Σ m O(m)
Так что в некотором смысле нет краткого способа указать все перестановки слова.
Вот простое доказательство нижней оценки на размер регулярного выражения для языка всех перестановок алфавита размера . Поскольку регулярное выражение размера можно преобразовать в NFA с состояниями , достаточно дать нижнюю границу для NFA.Ω~(2n) Σ n m O(m)
Мы будем использовать метод набора дурака , который мы сейчас опишем. Пусть - язык, и пусть - набор пар слов, таких что:L (xi,yi)1≤i≤N
Тогда каждый NFA для содержит хотя бы состояний. Действительно, рассмотрим любой НКА для . Для каждого рассмотрим некоторые принимающие вычисления , и пусть будет состоянием, в котором находится NFA после чтения в этом принимающем вычислении. Я утверждаю, что для . Действительно, если то «вырезать и вставить» показывает, что и находятся в , вопреки предположению.L N L i xiyi qi xi qi≠qj i≠j qi=qj xiyj xjyi L
Теперь мы можем доказать нижнюю оценку NFA для языка всех перестановок символов ; для простоты изложения мы предполагаем, что четно. Для каждого подмножества из размера , пусть состоит из всех символов в в некотором произвольном порядке, а состоит из всех символов не в в некотором произвольном порядке. Ясно, что . И наоборот, если то . Это показывает, что каждый NFA дляLn σ1,…,σn n S σ1,…,σn n/2 xS S yS S xSyS∈Ln S≠T xSyT∉Ln Ln содержит как минимум много состояний.(nn/2)=Ω(2n/n−−√)
источник
Почему нет способа написать «перестановка» в регулярных выражениях
Перестановка регулярного, бесконечного языка (бесконечного количества слов) не обязательно регулярна. Таким образом, это не может быть записано как регулярное выражение.
доказательство
Подумайте о языке
(ab)*
. (Пример вдохновлен Дэвидом Ричерби .) Одна из его перестановок -a*b*
. Это не обычный язык. ч.т.д..источник