Разве современные диалекты регулярных выражений не являются регулярными?

Первое, что приходит на ум, это обратные ссылки:

(\w*)\s\1

(соответствует группе словесных символов, за которой следует символ пробела, а затем та же группа, которая ранее соответствовала), например: hello hello соответствует, hello world нет.

Эта конструкция не является регулярной (т. е. не может быть сгенерирована с помощью обычной грамматики).

Еще одна необычная функция, поддерживаемая Perl Compatible RegExp (PCRE), — это рекурсивные шаблоны:

\((a*|(?R))*\)

Это можно использовать для сопоставления любой комбинации сбалансированных круглых скобок и "a" (из википедии).

Несколько примеров:

• Регулярные выражения поддерживают группировку. Например. в Ruby: /my (group)/.match("my group")[1] выведет «группу». для хранения чего-либо в группе требуется внешнее хранилище, которого нет у конечного автомата.
• Многие языки, например. C# поддерживает захваты, т. е. каждое совпадение будет захвачено в стеке — например, шаблон (?<MYGROUP>.)* может выполнять несколько захватов "." в той же группе.
• Группировка используется для обратной ссылки, как указано пользователем NullUserException выше. Для обратных ссылок требуется один или несколько внешних стеков с мощностью автомата проталкивания вниз (вы должны иметь возможность поместить что-то в стек, а затем просмотреть или извлечь его.
• Некоторые движки имеют возможность отдельно загружать и извлекать внешние стеки и проверять, пуст ли стек. В .NET на самом деле (?<MYGROUP>test) помещает стек в стек, а (?<-MYGROUP>) извлекает стек.
• Некоторые движки, такие как движок .NET, имеют концепцию сбалансированной группировки, когда внешний стек может быть отправлен и извлечен одновременно. Синтаксис сбалансированной группировки — (?<FIRSTGROUP-LASTGROUP>), который извлекает LASTGROUP и проталкивает захват, начиная с индекса LASTGROUP в стеке FIRSTGROUP. На самом деле это можно использовать для сопоставления бесконечно вложенных конструкций, что определенно выходит за рамки возможностей конечного автомата.

Вероятно, существуют и другие хорошие примеры :-) Если вас дополнительно интересуют некоторые детали реализации внешних стеков в сочетании с регулярными выражениями и сбалансированной группировкой и, следовательно, автоматами более высокого порядка, чем конечные автоматы, я однажды написал об этом две короткие статьи (http:/ /www.codeproject.com/KB/recipes/Nested_RegEx_explained.aspx и http://www.codeproject.com/KB/recipes/RegEx_Balanced_Grouping.aspx).

В любом случае, конечность или нет, я считаю, что сила, которую этот дополнительный материал привносит в обычные языки, велика :-)

бр. Мортен

Детерминированный или недетерминированный конечный автомат распознает только регулярные языки, которые описываются регулярными выражениями. Определение регулярного выражения простое. Пусть S — алфавит. Тогда пустой набор, пустая строка и каждый элемент S являются регулярными выражениями (над S). Пусть u и v — регулярные выражения. Затем объединение (u | v), конкатенация (uv) и замыкание (u*) < em>u и v являются регулярными выражениями над S. Это определение легко распространяется на обычные языки. Ни одно другое выражение не является регулярным выражением. Как уже отмечалось, некоторые обратные ссылки являются примером. Страницы Википедии, посвященные обычным языкам и выражениям, являются хорошими ссылками.

По сути, некоторые «регулярные выражения» не являются регулярными, потому что для их распознавания нельзя построить автомат определенного типа. Например, язык

{ a^ i b^ i : i <= 0 }

не является регулярным. Это связано с тем, что принимающему автомату потребуется бесконечно много состояний, но автомат, принимающий обычные языки, должен иметь конечное число состояний.