Regex Speed

[greg]

garrickp at gmail.com wrote:
> the author of this citation states that
> any regex can be expressed as a  DFA machine. However ...
 > I appear to have found one example of a regex
> which breaks this assumption.
> 
> "ab+c|abd"
> 
> Am I correct?

No. Any NFA can be converted to an equivalent DFA.
This is how scanner generators like Lex work -- they
first construct an NFA from the regex, and then
convert it to a DFA. Going directly from the regex
to a DFA, like you're trying to do, would be a lot
harder, and I'd be surprised if anyone ever does
it that way.

There's a description of the NFA-to-DFA algorithm
here:

http://www.gamedev.net/reference/articles/article2170.asp

--
Greg