[EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
