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

mtimmerm@microstar.com (Matt Timmermans)
22 Mar 1996 21:24:59 -0500

          From comp.compilers
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)
| List of all articles for this month |
From: mtimmerm@microstar.com (Matt Timmermans)
Newsgroups: comp.compilers
Date: 22 Mar 1996 21:24:59 -0500
Organization: Microstar Software Ltd.
References: 96-03-125
Keywords: DFA, theory

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


| Is it possible to transform any given non-deterministic regular
| expression into a deterministic regular expression?


You've already been chastised for the form of your question, so I won't
bother with that -- I know what you mean.


The answer to this question is no. Neither


(aa)*(ab|c) nor (a|b)*(ac|bd)


can be written deterministically.


| it seems not be possible to map any (non-)deterministic finte state
| autonama to a (non-)deterministic regular expression.


Any DFA or NFA can be written as a regular expression.


</Matt>


--------------------------------------------------------------
Matt Timmermans | Phone: +1 613 596-2233
Microstar Software Ltd. | Fax: +1 613 596-5934
3775 Richmond Rd. | E-mail: mtimmerm@microstar.com
Nepean Ontario CANADA K2H 5B7 | http://www.microstar.com
--

Post a followup to this message

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