Какие формальные языки могут анализировать современные механизмы регулярных выражений?

Здесь на SO люди иногда говорят что-то вроде «вы не можете анализировать X с помощью регулярных выражений, потому что X не является обычным языком». Насколько я понимаю, однако, современные механизмы регулярных выражений могут сопоставляться не только с регулярными языками в смысле Хомского . Мои вопросы:

учитывая механизм регулярных выражений, который поддерживает

  • обратные ссылки
  • обходные утверждения неограниченной ширины
  • рекурсия, например(?R)

какие языки он может анализировать? Может ли он анализировать любой свободный от контекста язык -, а если нет, то каким может быть контрпример?

(Чтобы быть точным, под «анализом» я подразумеваю «создание одного регулярного выражения, которое будет принимать все строки, сгенерированные грамматикой X, и отклонять все остальные строки» ).

Добавлять. :Мне особенно интересно увидеть пример свободного от контекста -языка, который современные механизмы регулярных выражений (Perl, Net, модуль регулярных выражений Python )не смогли бы проанализировать.

27
задан georg 7 July 2012 в 21:19
поделиться