多模式匹配自动机的构造与极小化

摘要

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.%通过给定的单模式构造出相应的模式匹配自动机，集成单模式匹配自动机而得到多模式非确定型有穷自动机（NFA）。将非确定型自动机转化为确定型自动机，在状态集上引入等价关系，对该确定型有穷自动机进行极小化，得到与原自动机功能等价的极小化自动机，从而使之能确定其中任意一个模式的所有匹配位置。