首页 | 本学科首页   官方微博 | 高级检索  
     


Obtaining shorter regular expressions from finite-state automata
Authors:Yo-Sub Han  Derick Wood  
Affiliation:

aSystem Technology Division, Korea Institute of Science and Technology, P.O. Box 131, Cheongnyang, Seoul, Republic of Korea

bDepartment of Computer Science, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong

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.
Keywords:Regular languages  Finite-state automata  State elimination  Bridge states  Vertical chopping  Horizontal chopping
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号