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

mark@omnifest.uwm.edu (Mark Hopkins)
27 Mar 1996 00:06:08 -0500

          From comp.compilers
Related articles
Re: Non-deter. regular expr. -> deter. regular exp mark@omnifest.uwm.edu (1996-03-27)
Re: Non-deter. regular expr. -> deter. regular exp mark@omnifest.uwm.edu (1996-03-27)
| List of all articles for this month |
From: mark@omnifest.uwm.edu (Mark Hopkins)
Newsgroups: comp.compilers
Date: 27 Mar 1996 00:06:08 -0500
Organization: Omnifest
Keywords: DFA

The following expression blows up exponentially into a DFA:


                                        (a + b)* a (a + b) ... (a + b)


When there are n copies of (a + b) the resulting DFA will have 2^{n+1}
states, but can easily be represented by an NFA of a linear number of
states.
--

Post a followup to this message

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