Generating all permutations from a regexp

[Chris Johnson]

Thomas Ploch wrote:
> Fredrik Lundh wrote:
> > Nick Craig-Wood wrote:
> >
> >> A regular expression matcher uses a state machine to match strings.
> >
> > unless it's the kind of regular expression matcher that doesn't use a
> > state machine, like the one in Python.
> >
> > </F>
> >
>
> How is the matching engine implemented then?
>
> I thought regular languages can be described by deterministic /
> non-deterministic finite state machines. I am just curious ...

Regular expressions are described by N?DFAs, but Perl-compatible
regular expressions (which pretty much every language implements now)
are not true regular expressions. They are actually Turing complete,
and thus have features that cannot be implemented in N?DFAs.