Не регулярны ли регулярные регулярные выражения?

Ответ 1

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

(\w*)\s\1

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

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

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

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

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

Ответ 2

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

• Регулярные выражения поддерживают группировку. Например. в Ruby: /my (group)/.match("my group")[1] выводит "группу". для хранения чего-либо в группе требуется внешнее хранилище, которое не имеет конечного автомата.
• Многие языки, например. С#, поддерживающие захваты, т.е. Что каждое совпадение будет записано в стеке - например, шаблон (?<MYGROUP>.)* может выполнять несколько захватов ".". в той же группе.
• Группировка используется для обратного вызова, как указано выше пользователем NullUserException. Для обратного вызова требуется один или несколько внешних стеков с силой push-down-automaton (вы должны иметь возможность толкать что-то в стеке и заглядывать или всплывать после этого.
• Некоторые двигатели имеют возможность отдельного нажатия и выталкивания внешних стеков и проверки того, пуст ли пуст. В .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).

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

Br. Morten

Ответ 3

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

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

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

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