Yo-Sub Han
How to compute better regular expressions from finite-state automata
HKUST

Date: Friday September 17, 2004
Time 11-12
Venue: Room 3464 


Abstract
It is well known that the family of languages specified by finite-state
automata is same as the languages described by regular expressions.

In this talk, we present two well known automaton constructions and one
new construction by Ilie and Yu to show that we can make a finite-state
automaton from a given regular expression. Then, we re-introduce the state
elimination to show that we can compute a regular expression from a given
finite-state automaton. We propose some heuristics based on the structural
property of a given automaton in state elimination; they guarantee a
better regular expression.


This is joint work with Derick Wood