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

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

Другими словами, с учетом шаблона S, содержащего ненадежный квантор, можно ли этот шаблон переписать в эквивалентный шаблон T, который не содержит ненужных кванторов?

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

8
задан uckelman 20 July 2011 в 18:34
поделиться