27 Mar 1996 00:06:08 -0500

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

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.