| 多模式匹配自动机的构造与极小化 |
| |
| 引用本文： | 张丽.多模式匹配自动机的构造与极小化[J].铜仁学院学报,2011,13(3):129-131. |
| |
| 作者姓名： | 张丽 |
| |
| 作者单位： | 贵州大学计算机科学与信息学院,贵州贵阳,550025 |
| |
| 基金项目： | 贵州省自然科学基金，贵大人才引进基金项目 |
| |
| 摘 要： | 通过给定的单模式构造出相应的模式匹配自动机，集成单模式匹配自动机而得到多模式非确定型有穷自动机（NFA）。将非确定型自动机转化为确定型自动机，在状态集上引入等价关系，对该确定型有穷自动机进行极小化，得到与原自动机功能等价的极小化自动机，从而使之能确定其中任意一个模式的所有匹配位置。
|
| 关 键 词： | 有穷自动机 多模式匹配 等价关系 极小化 |
Construction and Minimization of Multi-Pattern Matching Automata |
| |
| ZHANG Li.Construction and Minimization of Multi-Pattern Matching Automata[J].Journal of Tongren University,2011,13(3):129-131. |
| |
| Authors: | ZHANG Li |
| |
| Institution: | ZHANG Li(College of Computer Science and Information,Guizhou University,Guiyang,Guizhou 550025,China) |
| |
| Abstract: | To a given single pattern, a corresponding pattern matching automata can be constructed. By integrating single pattern matching automates, a multi-pattern non-deterministic finite automata （NFA） can be acquired. We change the non-deterministic automata into deterministic automata, and minimize it by introducing equivalence relation on state suites. Since the acquired minimal automaton is equivalent to the original automata in function, it can determine all location where any one of pattern appears. |
| |
| Keywords: | finite automaton multi-pattern matching equivalence relation minimization |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
