Re: Non-deter. regular expr. -> deter. regular expr.

Frans F.J. Faase wrote:
> Is it possible to transform any given non-deterministic regular
> expression into a deterministic regular expression? I know it is
> possible to map each non-deterministic finite state autonama to a
> deterministic finite state autonama, but it seems not be possible to
> map any (non-)deterministic finte state autonama to a
> (non-)deterministic regular expression.


  [examples of what he wants to do]


> non-deter. | deter.
> --------------------------+------------------------
> ( a b | a c ) | a ( b | c ) (1)
> [ a ] a | a [ a ] (2)
> a* a | a+ (3)
> [ a | b | c ] a | (a [ a ]) | ( ( b | c ) a ) (4)
> ( a | b | c )* a | ( a | ( ( b | c )* a ))* (5)




The question as posed is meaningless: There is no definition I've ever
seen for a "[non]deterministic" regular expression.


Determinism and non-determinism are descriptions of execution models
for abstract machines. Regular expressions are not abstract machines;
they are compact, recursive descriptions of sets of strings. In this
way, they are like grammars - in fact, they are exactly equivalent to
regular grammars. One could apply notions from the theory of
grammers. For example:


ambiguous non-ambiguous
-------------------------------------
a* a* a*


Ambiguity can be defined in terms of the underlying grammar (which can
be turned into a description in terms of the RE), and it's a
structural property; but all the examples above are
"non-deterministic" only if you choose a particular interpretation of
the RE's as an execution model. This is most obvious in case 2: These
two can only differ if you assume that matching must be done from left
to right. But of course one can as easily define a matcher for RE's
that scans the string from right to left! In that case, would you
switch the two columns?


The same swapping "determinizes" all the examples but (5) - but (5) is
an incorrect transformation, as the right hand side can match the
empty string, while the left hand side cannot. So I don't know what
to make of it.


Note that, just as there's no special reason to describe matching as
left to right, there's no reason to define it as starting at one end
or another. You could easily define a matcher that starts at the
middle of the string and tries to grow outward - going as far as it
can to the right and then to left; to the left and then to the right;
one step each in alternating directions; or what have you. For any
given RE, some of these choices will require non-determinism in the
"obvious" resulting FSM; some won't. (Of course, we know the
non-determinism can always be eliminated.)


Query: The basic construction gives you an NFSM whose size (number of
states) is linear in the size of the input. Converting that DFSM may
cause an exponential blowup in the number of states. (a) Are there
examples where the exponential blowup actually occurs, but would *not*
occur if scanning in some other order were allowed? (b) Are there RE's
whose expression as a DFSM *always* requires an exponential blowup, no
matter what order you allow scanning in? (I'd guess the answer to (b)
is yes. I suppose one might call such an RE "non-deterministic"!)


                                                                                                                -- Jerry


--

Return to the comp.compilers page.
Search the comp.compilers archives again.