构造型的D2FA生成算法
(0) Delayed input DFA (D2FA)中引入默认边来对确定状态机(DFA)进行状态转移精简。为了提高D2FA生成算法的效率,本文分析了对正则表达式X得到的DFA(∧X)与DFA(X)间的相关性,提出一种从DFA(∧X)到D2FA(X)的构造型算法。该算法将DFA(X)中的状态用DFA(∧X)中的状态序列进行表示,从而基于状态序列进行默认边的选择,而不需要生成实际的DFA(X)。理论分析和实验结果表明,该算法降低了构造D2FA的算法复杂度,同时仍能保证进行模式匹配时的解析时间下限,以及对DFA的状态转移精简能力。
通信网络 确定状态机 模式匹配 程序设计
周颢 刘振华 赵保华
中国科学技术大学,计算机科学与技术系,合肥,230027 安徽省计算与通讯软件重点实验室,合肥,230027
国内会议
南京
中文
40-43,48
2009-04-24（万方平台首次上网日期，不代表论文的发表时间）