3College of Computer Science & Technology, BUPT
从 有限自动机 构造等价的正则表达式
(状态消去法)
思路 :
(1) 扩展自动机的概念,允许正则表达式作为转移弧的标
记 . 这样,就有可能在消去某一中间状态时,保证自动机能
够接受的字符串集合保持不变 .
(2) 在消去某一中间状态时,与其相关的转移弧也将同时
消去,所造成的影响将通过修改从每一个前趋状态到每一个
后继状态的转移弧标记来弥补 .
以下分别介绍中间状态的消去与正则表达式构造过程 .