Предположим, у меня есть язык регулярных выражений, поддерживающий литералы, классы положительных и отрицательных символов, упорядоченное чередование и жадные квантификаторы ?
, *
и +
. (Это, по сути, подмножество PCRE без обратных ссылок, проверочных утверждений или некоторых других более причудливых битов.) Добавляются ли нечеткие квантификаторы ??
, *?
и +?
увеличивают выразительную мощь этого формализма?
Другими словами, с учетом шаблона S, содержащего ненадежный квантор, можно ли этот шаблон переписать в эквивалентный шаблон T, который не содержит ненужных кванторов?
Если этот вопрос был рассмотрен в литературе, я был бы признателен за любые ссылки, которые может предоставить кто-нибудь. Мне не удалось найти почти никаких теоретических работ о выразительной силе расширенного регулярного выражения формализмов (помимо обычных вещей о том, как обратные ссылки уводят вас от обычные языки в контекстно-свободные грамматики).