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

neumann@PSI.Uni-Trier.DE (Andreas Neumann)
22 Mar 1996 21:25:48 -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: neumann@PSI.Uni-Trier.DE (Andreas Neumann)
Newsgroups: comp.compilers
Date: 22 Mar 1996 21:25:48 -0500
Organization: Compilers Central
References: 96-03-125
Keywords: DFA, theory, bibliography

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


> Is it possible to transform any given non-deterministic regular
> expression into a deterministic regular expression? I know it is


In
      A. Brueggemann-Klein, D. Wood: "Deterministic Regular Languages",
      STACS 1992, LNCS 577, pp. 173-184


it is shown that the class of deterministic regular languages is a proper
subset of the regular languages. There are regular languages which can
not be denoted by any deterministic regular expression. An example is


    (a|b)*a(a|b)


which has no deterministic equivalent.


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


Is this really deterministic? Shouldn't it be


                                                                ( a | ( ( b | c ) ( b | c )* a ) )* ?


Andreas.


--
Andreas Neumann Praktische Informatik II
                                                                                            FB IV, Abt. Informatik
Tel. : +49 651 201-2823 University of Trier
email: neumann@psi.uni-trier.de D-54286 Trier, Germany




--

Post a followup to this message

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