构造型的D2FA生成算法

摘要：

Delayed input DFA (D2FA)中引入默认边来对确定状态机(DFA)进行状态转移精简. 为了提高D2FA生成算法的效率,分析了对正则表达式X得到的DFA(∧X)与DFA(X)间的相关性,提出一种从DFA(∧X)到D2FA(X)的构造型算法. 该算法将DFA(X)中的状态用DFA(∧X)中的状态序列进行表示,从而基于状态序列进行默认边的选择,而不需要生成实际的DFA(X).理论分析和实验结果表明,该算法降低了构造D2FA的算法复杂度,同时仍能保证进行模式匹配时的解析时间下限,以及对DFA的状态转移精简能力.

关键词：确定状态机、D2FA、默认边

所属期刊栏目：32

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金项目60872009,60602016;国家"863计划"项目2007AA01Z428,2009AA01Z148;安徽高校省级自然科学研究计划重大项目ZD2008005-2,ZD200904,JK2009A013,JK2009A025

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

页数：共5页

页码：40-43,48