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

摘要

从确定型有限自动机生成简短的正则表达式是计算机理论研究的基础问题之一,经典生成方法对状态排序方式比较敏感,不能保证表达式的生成质量.为了找到最优状态序列,基于状态消减法,提出了一种向前预测的改进权重法.该算法利用权重函数分析消减状态前和消减状态后自动机字符总量的变化,并结合并行消减状态策略,以及连续消减多个状态的向前预测策略,从而确定状态序列.通过实验将改进权重法与现有的启发式搜索算法进行对比,结果显示该算法所生成最优正则表达式的正确率高于其他算法.