Regular Expression Matching Can Be Simple and Fast (2007)

The two graphs plot the time required by each approach to match the regular expression n n against the string n.

Notice that Perl requires over sixty seconds to match a 29-character string. As a simple example, here is a machine recognizing the set of strings matched by the regular expression :

A finite automaton is always in one of its states, represented in the diagram by circles. This NFA is equivalent to the previous two, but the unlabeled arrow makes the correspondence with clearest:

Regular expressions and NFAs turn out to be exactly equivalent in power: every regular expression has an equivalent NFA (they match the same strings) and vice versa.

Source: swtch.com