欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
Delayed input DFA（D^2FA）中引入默认边来对确定状态机（DFA）进行状态转移精简。为了提高D^2FA生成算法的效率，分析了对正则表达式X得到的DFA（∧X）与DFA（X）间的相关性，提出一种从DFA（∧X）到D^2FA（X）的构造型算法。该算法将DFA（X）中的状态用DFA（∧X）中的状态序列进行表示，从而基于状态序列进行默认边的选择，而不需要生成实际的DFA（X）。理论分析和实验结果表明，该算法降低了构造DZFA的算法复杂度，同时仍能保证进行模式匹配时的解析时间下限，以及对DFA的状态转移精简能力。
英文摘要：
Delayed input deterministic finite automata （D^2FA） reduces the transition edges of de- terministic 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 D^2FA. A constructing algorithm is presented to create D^2FA 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 D^2FA, meanwhile it ensures a lower time bounds of pattern match and capacity of reducing state transition.
同期刊论文项目
同项目期刊论文
期刊信息
位置：