Are .NET's regular expressions Turing complete?

Question

Regular expressions are often pointed to as the classical example of a language that is not Turning complete. For example "regular expressions" is given in as the answer to this SO question looking for languages that are not Turing complete.

In my, perhaps somewhat basic, understanding of the notion of Turning completeness, this means that regular expressions cannot be used check for patterns that are "balanced". Balanced meaning have an equal number of opening characters as closing characters. This is because to do this would require you to have some kind of state, to allow you to match the opening and closing characters.

However the .NET implementation of regular expressions introduces the notion of a balanced group. This construct is designed to let you backtrack and see if a previous group was matched. This means that a .NET regular expressions:

^(?<p>a)*(?<-p>b)*(?(p)(?!))$

Could match a pattern that:

ab
aabb
aaabbb
aaaabbbb
... etc. ...

Does this means .NET's regular expressions are Turing complete? Or are there other things that are missing that would be required for the language to be Turing complete?

Answer 1

In computation theory, a regular expression describes a regular language. The class of regular languages is precisely those languages that can be recognized by some finite state machine, or generated by a regular grammar. However, the example you have described (balanced phrases) is not a regular language and cannot be recognized by a finite state machine or generated by a regular grammar. In fact, this a textbook example of what is called a context-free language. These require a push-down automata for recognition. The class of context-free languages is a superset of regular languages but a proper subset of turing complete languages. The syntax (as opposed to semantics) of most programming languages is a context-free language. If you are interested in learning more about this topic, you can start with the Chomsky hierarchy