20 Mar 1996 23:26:39 -0500

Related articles |
---|

Non-deter. regular expr. -> deter. regular expr. faase@cs.utwente.nl (1996-03-20) |

Re: Non-deter. regular expr. -> deter. regular expr. leichter@smarts.com (Jerry Leichter) (1996-03-22) |

Re: Non-deter. regular expr. -> deter. regular expr. mtimmerm@microstar.com (1996-03-22) |

Re: Non-deter. regular expr. -> deter. regular expr. neumann@PSI.Uni-Trier.DE (1996-03-22) |

Re: Non-deter. regular expr. -> deter. regular expr. ikastan@alumnae.caltech.edu (1996-03-24) |

Re: Non-deter. regular expr. -> deter. regular exp mark@omnifest.uwm.edu (1996-03-27) |

From: | faase@cs.utwente.nl (Frans F.J. Faase) |

Newsgroups: | sci.math,comp.compilers,comp.programming |

Date: | 20 Mar 1996 23:26:39 -0500 |

Organization: | University of Twente, Dept. of Computer Science |

Keywords: | DFA, theory, question |

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/ ---------------------

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.