Warp wrote:
>   Any regular expression can be converted into a state machine, but can
> every state machine be converted into a regular expression? Is there a
> one-to-one relation?

In the original definitions of those two terms, yes. Obviously, by the time 
you get to Perl regular expressions, they're no longer "regular" in the same 
sense. If you stick to regular expression algebra as invented by Kleene, 
they're equivalent specifications of the same languages. (One can wind up 
exponentially larger than the other, mind.)

-- 
   Darren New, San Diego CA, USA (PST)
   The NFL should go international. I'd pay to
   see the Detroit Lions vs the Roman Catholics.

Post a reply to this message