Han, Yo-Sub Wood, Derick 2024-01-21T01:32:38Z 2024-01-21T01:32:38Z 2021-09-05 2007-02-12 0304-3975 https://pubs.kist.re.kr/handle/201004/134651 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. (c) 2006 Elsevier B.V. All rights reserved. English ELSEVIER Obtaining shorter regular expressions from finite-state automata Article 10.1016/j.tcs.2006.09.025 1 THEORETICAL COMPUTER SCIENCE, v.370, no.1-3, pp.110 - 120 THEORETICAL COMPUTER SCIENCE 370 1-3 110 120 scie scopus 000244214900008 2-s2.0-33846365658 Computer Science, Theory & Methods Computer Science Article regular languages finite-state automata state elimination bridge states vertical chopping horizontal chopping