20 Aug 2003 01:34:23 -0400

Related articles |
---|

Announcing PyGgy newsham@lava.net (Tim Newsham) (2003-08-15) |

finite state minimization proofs rpboland@math.uwaterloo.ca (Ralph P. Boland) (2003-08-20) |

Re: finite state minimization proofs derkgwen@HotPOP.com (Derk Gwen) (2003-08-23) |

From: | "Ralph P. Boland" <rpboland@math.uwaterloo.ca> |

Newsgroups: | comp.compilers |

Date: | 20 Aug 2003 01:34:23 -0400 |

Organization: | University of Waterloo |

References: | 03-08-053 |

Keywords: | DFA, theory, question |

Posted-Date: | 20 Aug 2003 01:34:22 EDT |

Where can I find the simplest proofs that

the algorithms for finite state machine minimiztion

are correct; i.e. that the machine constructed has

the fewest number of states?

I am looking for a proof for the algorithm that is

O(n\log n) for an n state input.

I would also be interested in a proof for the O(n^2) algorithm.

Are there publicly available standard implementations

of these algorithms and the algorithm for constructing

a FSM from a regular expression if so where?

Are there implementations of these algorithms or variations of

them that are particularly fast and if so where?

I am designing an algorithm for constructing a minimum

state FSM directly from a regular expression and I

will want to compare my algorithms and proofs with

the competing proofs/algorithms.

Thanks

Ralph

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.