与有限自动机等价的正规表达式的构造算法研究

摘要

有限自动机(FA)和正规表达式(RE)都是正则语言(RL)的描述模型.FA擅长语言的识别,而RE比FA更简单,更容易处理,而且这种表达式更容易,更接近语言的集合表示和语言的计算机表示,因此,RE使用起来更方便一些.RE已经被广泛地应用于文本检索系统,数据库查询语言等.例如KMP匹配算法,UNIX中的grep命令都是RE的具体应用.