Non-deter. regular expr. -> deter. regular expr.

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.


The regular expressions I look at are described by the following
grammar:


      E ::= a | b | c | ...
              | E E
              | [ E ] -- optional
              | ( E )
              | E+ -- one or more times repeated
              | E* -- zero or more times repeated


My intuition says that is must be possible to map non-deter. regular
expressions to deterministic ones, see some examples:


        non-deter. | deter.
--------------------------+------------------------
        ( a b | a c ) | a ( b | c )
        [ a ] a | a [ a ]
            a* a | a+
        [ a | b | c ] a | (a [ a ]) | ( ( b | c ) a )
        ( a | b | c )* a | ( a | ( ( b | c )* a ))*


These examples seem to cover all possible non-deterministic
expressions, but will it still work if they occur in more complicated
combinations, e.g., can these rules be used as rewriting rules that
will work for any non-deterministic expression (without looping)?


Frans


--
Frans J. Faase
Information Systems Group Tel : +31-53-4894232
Department of Computer Science secr. : +31-53-4893690
University of Twente Fax : +31-53-4892927
PO box 217, 7500 AE Enschede, The Netherlands Email : faase@cs.utwente.nl
--------------- http://www.cs.utwente.nl/~faase/ ---------------------
--

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