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