Are .NET's regular expressions Turing complete?

Posted by Robert on Stack Overflow See other posts from Stack Overflow or by Robert
Published on 2011-01-29T06:52:46Z Indexed on 2011/01/29 7:26 UTC
Read the original article Hit count: 249

Filed under:

.NET

|

regex

|

computer-science

|

turing-machines

|

turing-complete

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?

© Stack Overflow or respective owner

Related posts about .NET

Apt-Get Update: failure to fetch; can't connect to any sources

as seen on Ask Ubuntu - Search for 'Ask Ubuntu'
I realize there are dozens of "apt-get update: failure to fetch" questions (I read through all I could find), but my present circumstance is unique to 12.04 and it affects all sources; not just launchpad. Additionally, I've tried several different servers in Europe and the U.S. as well as the "main… >>> More
12.04: Apt-Get Update: failure to fetch; can't connect to any sources

as seen on Ask Ubuntu - Search for 'Ask Ubuntu'
I realize there are dozens of "apt-get update: failure to fetch" questions (I read through all I could find), but my present circumstance is unique to 12.04 and it affects all sources; not just launchpad. Additionally, I've tried several different servers in Europe and the U.S. as well as the "main… >>> More
What's New in ASP.NET 4

as seen on Geeks with Blogs - Search for 'Geeks with Blogs'
The .NET Framework version 4 includes enhancements for ASP.NET 4 in targeted areas. Visual Studio 2010 and Microsoft Visual Web Developer Express also include enhancements and new features for improved Web development. This document provides an overview of many of the new features that are included… >>> More
.NET Reflector 6, .NET Reflector Pro, TestDriven.NET, .NET 4.0 and Mono

as seen on Simple Talk - Search for 'Simple Talk'
By now you may well have noticed that .NET Reflector 6 and .NET Reflector Pro are out in the wild. The official launch happened today, although we actually put the software out last Thursday as part of a phased release plan to ensure that everything went smoothly today which, so far, it seems to have… >>> More
Redmine on Apache2 with Passenger issue

as seen on Server Fault - Search for 'Server Fault'
I installed Redmine and run it in Apache2 with the Passenger module. Apache2 boots, Passenger module gets loaded and the Redmine welcome page is shown, however when trying to login or navigate to other parts of the Redmine site, the browser keeps loading and loading and loading forever, although the… >>> More

Related posts about regex

Find multiple regex in each line and skip result if one of the regex doesn't match

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a list of variables: variables = ['VariableA', 'VariableB','VariableC'] which I'm going to search for, line by line ifile = open("temp.txt",'r') d = {} match = zeros(len(variables)) for line in ifile: emptyCells=0 for i in range(len(variables)): regex = r'('+variables[i]+r')[:|=|\(](-… >>> More
OWASP Regex Repository: Is this regex correct?

as seen on Stack Overflow - Search for 'Stack Overflow'
I was looking at the regular expression for validating various data types from the (OWASP Regex Repository). One of the regular expressions in there is called safetext and looks like: ^[a-zA-Z0-9\s.\-]+$ My first question is: Is this regular expression correct? complementary question If this… >>> More
Make a Perl-style regex interpreter behave like a basic or extended regex interpreter

as seen on Stack Overflow - Search for 'Stack Overflow'
I am writing a tool to help students learn regular expressions. I will probably be writing it in Java. The idea is this: the student types in a regular expression and the tool shows which parts of a text will get matched by the regex. Simple enough. But I want to support several different regex… >>> More
JS regex isn't matching, even thought it works with a regex tester

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm writing a piece of client-side javascript code that takes a function and finds the derivative of it, however, the regex that's supposed to match with the power rule fails to work in the context of the javascript program, even though it sucessfully matches when it's used with an independent regex… >>> More
c# RegEx with "|"

as seen on Stack Overflow - Search for 'Stack Overflow'
I need to be able to check for a pattern with | in them. For example an expression like d*|*t should return true for a string like "dtest|test". I'm no regex hero so I just tried a couple of things, like: Regex Pattern = new Regex("s*\|*d"); //unable to build because of single backslash Regex Pattern… >>> More