# Optimizing Regular Expressions

Optimizing regular expressions is an exceptionally complex field. A vast majority of the problems within this field is `NP`

or `NP-COMPLETE`

. Meaning that their solutions cannot be bound (time/space) under any definite polynomial.

All APIs (such as: .NET, PHP, ASP (classic VB really), JavaScript) that support regular expressions performs some form of **equivalence reduction** meaning it tries to reduce the given regular expression into a reduced YET equivalent regular expression. Of course there is no full-proof way of doing this for couple of reasons: (1) There is no way to guarantee that a reduced regular expression is the most efficient regular expression possible. At this moment there is no GENERAL way of proving that.

I am writing about this topic because I am in the process of learning ASP.NET and I was just testing some of it’s regular expression capabilities so I tried (as you can see I wasn’t thinking):

```
([a-z]+)*!
```

And it took longer than I thought. As soon as I changed the regular expression to the equivalent regular expression:

```
([a-z])*!
```

It ran much much faster. This is a special case of nesting the Kleene star (*) which always takes precedence over the (+) operator. Most text-books actually don’t even define the (+) operator because it can be simplied to the following:

```
a+ = aa*
```or in our case```
[a-z]+ = [a-z][a-z]*
```If we take it a little futher we get:```
([a-z]+)*!
= ([a-z][a-z]*)*!
= ([a-z]*[a-z]*)!
= [a-z]*! (COMPLEX STEP)
```

The last step I would assume is where .NET couldn’t reduce any further. The last step although easy to see why they are equivalent it’s hard to develop a general algorithm to detect that.