&gt; &lt;sub&gt;_This is the second part of a series of educational regex articles. It shows how lookaheads and nested references can be used to match the non-regular languge a&lt;sup&gt;n&lt;/sup&gt;b&lt;sup&gt;n&lt;/sup&gt;. Nested references are first introduced in: [How does this regex find triangular numbers?][p1]_&lt;/sub&gt;

One of the archetypal non-[regular languages][wrl] is:

&gt; `L = { a`&lt;sup&gt;n&lt;/sup&gt;`b`&lt;sup&gt;n&lt;/sup&gt;` : n &gt; 0 }`  

This is the language of all non-empty strings consisting of some number of `a`&#39;s followed by an equal number of `b`&#39;s. Examples of strings in this language are `ab`, `aabb`, `aaabbb`.

This language can be show to be non-regular by the [pumping lemma][wpl]. It is in fact an archetypal [context-free language][wcfl], which can be generated by the [context-free grammar][wcfl] `S → aSb | ab`.

Nonetheless, modern day regex implementations clearly recognize more than just regular languages. That is, they are not &quot;regular&quot; by formal language theory definition. PCRE and Perl supports recursive regex, and .NET supports balancing groups definition. Even less &quot;fancy&quot; features, e.g. backreference matching, means that regex is not regular.

But just how powerful is this &quot;basic&quot; features? Can we recognize `L` with Java regex, for example? Can we perhaps combine lookarounds and nested references and have a pattern that works with e.g. [`String.matches`](http://download.oracle.com/javase/6/docs/api/java/lang/String.html#matches%28java.lang.String%29) to match strings like `ab`, `aabb`, `aaabbb`, etc?

### References

* [perlfaq6: Can I use Perl regular expressions to match balanced text?](http://perldoc.perl.org/perlfaq6.html#Can-I-use-Perl-regular-expressions-to-match-balanced-text?)
* [MSDN - Regular Expression Language Elements - Balancing Group Definitions](http://msdn.microsoft.com/en-us/library/bs2twtah.aspx#balancing_group_definition)
* [pcre.org - PCRE man page](http://www.pcre.org/pcre.txt)
* [regular-expressions.info](http://www.regular-expressions.info/) - [Lookarounds](http://www.regular-expressions.info/lookaround.html) and [Grouping and Backreferences](http://www.regular-expressions.info/brackets.html)
* [`java.util.regex.Pattern`](http://java.sun.com/javase/6/docs/api/java/util/regex/Pattern.html)

### Linked questions

* [Does lookaround affect which languages can be matched by regular expressions?](https://stackoverflow.com/questions/2974210/does-lookaround-affect-which-languages-can-be-matched-by-regular-expressions)
* [.NET Regex Balancing Groups vs PCRE Recursive Patterns](https://stackoverflow.com/questions/3349999/net-regex-recursive-patterns)

[p1]: https://stackoverflow.com/questions/3627681/how-does-this-regex-find-triangular-numbers/
[wrl]: http://en.wikipedia.org/wiki/Regular_language
[wpl]: http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
[wcfg]: http://en.wikipedia.org/wiki/Context-free_grammar
[wcfl]: http://en.wikipedia.org/wiki/Context-free_language
[wpcre]: http://en.wikipedia.org/wiki/Perl_Compatible_Regular_Expressions

All Nested Reference Solutions on Gang of Coders

Total of 1 Nested Reference Solutions

How can we match a^n b^n?