确定型有限自动机生成最短正则表达式的启发式算法研究

蒙祖祈

(东北石油大学 计算机与信息技术学院, 黑龙江 大庆 163318)

0 引言

正则表达式与确定型有限自动机同属于正则语言模型，具有相同的表达能力，可以等价地相互转换。虽然自动机容易转化为高效的计算机内部程序，但状态间复杂的变迁关系难于理解，无法在工程实践中直接用于语法规则的设计和交流。根据自动机生成易于阅读的正则表达式有助于正则语言的理解和应用，也可以更广泛地应用自动机学习的研究成果，是形式语言领域研究的一个经典问题。

将确定型有限自动机转换为正则表达式的经典方法主要有3种：状态消减法、Brzozowski代数法和传递闭包法[1]。这3种方法生成的表达式质量均具有很大的不确定性，容易生成冗长的正则表达式，给表达式的阅读和理解带来困难。其实，无论采用哪种正则表达式生成方法，结果表达式的不确定性都源于状态排序的差异，状态排序的优化是提高正则表达式质量的关键。

目前，针对状态排序优化问题出现一批启发式状态排序算法，在一定程度上提高了结果表达式的质量。依据启发信息的类型，现有启发式排序算法可以分为结构特征算法和局部特征算法两类。结构特征算法由自动机拓扑结构决定状态顺序，包括桥状态法、回路计算法和嵌套回路法；局部特征算法根据状态自身及邻接状态决定状态顺序，包括流量法、静态度乘积法、动态度乘积法和权重法。具体算法介绍请参照文献[2]。……