构造正则表达式的最佳NFA算法的选择

摘要：

介绍了工程中广泛应用的四种经典和先进的不确定有限自动机NFA的基本构造方法,它们是位置自动机Apos部分派生自动机Apd,跟随自动机Af,共同跟随集合自动机Acfs.列举大量工程实践中常用和经典的正则表达式,分别用上述自动机算法进行求解实验,对它们的运算尺寸以及与正则表达式尺寸之间的关系,列出表格分别进行比较分析,从中总结出各种自动机的构造特点和最佳应用场合.针对如何根据不同的正则表达式来选择非确定性有限自动机NFA算法提供了重要的参考依据.

关键词：正则表示式、非确定性有限自动机(NFA)、算法

所属期刊栏目：6

分类号：TP301.1(计算技术、计算机技术)

在线出版日期：2007-07-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：58-61