Как мы можем сопоставить ^ nb ^ n с регулярным выражением Java?

_{Это вторая часть серии образовательных регулярных выражений. Он показывает, как можно использовать предпросмотры и вложенные ссылки для сопоставления с нерегулярным языком a ⁿ b ⁿ . Вложенные ссылки впервые введены в: Как это регулярное выражение находит треугольные числа?}

Один из архетипических не регулярных языков :

L = {a ⁿ b ⁿ : n> 0}

Это язык всех непустых строк, состоящих из некоторого числа a , сопровождаемых равным числом б 'ы. Примерами строк на этом языке являются ab , aabb , aaabbb .

Этот язык можно показать как нерегулярный с помощью леммы прокачки . Фактически это архетипический контекстно-свободный язык , который можно сгенерировать с помощью контекстно-свободной грамматики S → aSb | ab .

Тем не менее, современные реализации регулярных выражений явно распознают не только обычные языки. То есть они не являются «регулярными» по формальному определению теории языка. PCRE и Perl поддерживают рекурсивное регулярное выражение, а .NET поддерживает определение групп балансировки. Еще менее «причудливые» функции, например сопоставление с обратными ссылками, означают, что регулярное выражение не является регулярным.

Но насколько мощны эти «базовые» функции? Можем ли мы распознать L с помощью регулярного выражения Java, например? Можем ли мы объединить внешние ссылки и вложенные ссылки и иметь шаблон, который работает, например, с String.matches для сопоставления строк, таких как ab , aabb , aaabbb и т. Д.?

Ссылки

• perlfaq6: Можно ли использовать регулярные выражения Perl для соответствия сбалансированному тексту?
• MSDN - элементы языка регулярных выражений - определения балансировочной группы
• pcre.org - справочная страница PCRE
• регулярные-выражения.info - внешние источники и Группировка и обратные ссылки
• java.util.regex.Pattern

Связанные вопросы

• Влияет ли lookaround на то, какие языки можно сопоставлять с помощью регулярных выражений?
• .NET балансировочные группы регулярных выражений и рекурсивные шаблоны PCRE