Abstract
We consider the use of state elimination to construct shorter regular expressions from finite-state automata (FAs). Although state elimination is an intuitive method for computing regular expressions from FAs, the resulting regular expressions are often very long and complicated. We examine the minimization of FAs to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given FAs. We prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. In addition, we suggest heuristics for state elimination that leads to shorter regular expressions based on vertical chopping and horizontal chopping.
| Original language | English |
|---|---|
| Pages (from-to) | 110-120 |
| Number of pages | 11 |
| Journal | Theoretical Computer Science |
| Volume | 370 |
| Issue number | 1-3 |
| DOIs | |
| Publication status | Published - 2007 Feb 12 |
Bibliographical note
Funding Information:Han was supported by the Research Grants Council of Hong Kong Competitive Earmarked Research Grant HKUST6197/01E and the KIST Tangible Space Initiative Grant 2E19020. Wood was supported by the Research Grants Council of Hong Kong Competitive Earmarked Research Grant HKUST6197/01E.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)