| 构造型的D2FA生成算法 |
| |
| 引用本文： | 周颢,刘振华,赵保华.构造型的D2FA生成算法[J].北京邮电大学学报,2009,32(Z1):40-43. |
| |
| 作者姓名： | 周颢 刘振华 赵保华 |
| |
| 作者单位： | 1. 中国科学技术大学 计算机科学与技术系; 2. 安徽省计算与通讯软件重点实验室 |
| |
| 基金项目： | 国家自然科学基金，国家高技术研究发展计划(863计划)，安徽高校省级自然科学研究计划重大项目 |
| |
| 摘 要： | Delayed input DFA (D2FA)中引入默认边来对确定状态机(DFA)进行状态转移精简. 为了提高D2FA生成算法的效率，分析了对正则表达式X得到的DFA(∧X)与DFA(X)间的相关性，提出一种从DFA(∧X)到D2FA(X)的构造型算法. 该算法将DFA(X)中的状态用DFA(∧X)中的状态序列进行表示，从而基于状态序列进行默认边的选择，而不需要生成实际的DFA(X). 理论分析和实验结果表明，该算法降低了构造D2FA的算法复杂度，同时仍能保证进行模式匹配时的解析时间下限，以及对DFA的状态转移精简能力.
|
| 关 键 词： | 确定状态机 D2FA 默认边 |
| 收稿时间： | 2009-04-13 |
Research of Constructing Algorithm to Create D2FA |
| |
| ZHOU Hao,LIU Zhen-hua,ZHAO Bao-hua.Research of Constructing Algorithm to Create D2FA[J].Journal of Beijing University of Posts and Telecommunications,2009,32(Z1):40-43. |
| |
| Authors: | ZHOU Hao LIU Zhen-hua ZHAO Bao-hua |
| |
| Abstract: | Delayed input deterministic finite automata (D2FA) reduces the transition edges of deterministic finite automata (DFA) by introducing default edges. The relevance between DFA(∧X)and DFA(X) is analyzed to improve the efficiency of constructing algorithm to create D2FA. A constructing algorithm is presented to create D2FA from DFA. The algorithm expresses the state of DFA(X) with the state sequence of DFA(∧X), hence the choice of default edges is relayed on the state sequence, rather than creating actual DFA(X). Experiments show that the algorithm greatly reduces the complexity of constructing D2FA, meanwhile it ensures a lower time bounds of pattern match and capacity of reducing state transition. |
| |
| Keywords: | D2FA |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《北京邮电大学学报》浏览原始摘要信息 |
|
点击此处可从《北京邮电大学学报》下载全文 |
