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

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

作者：袁满;袁真

作者机构：合肥工业大学,计算机与信息学院,安徽,合肥,230009;合肥工业大学,计算机与信息学院,安徽,合肥,230009

来源：广州职业教育论坛

ISSN：2095-364X

年：2007

卷：006

期：002

页码：58-61

页数：4

中图分类：TP301.1

正文语种：chi

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

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