Abstract:

In order to reduce the number of non-deterministic finite automata (NFA) states, the preorder relation was introduced. The transition diagram for the NFA was regarded as a directed graph with signs based on graph theory,and then a new method of NFA minimization was proposed. Compared with the current NFA minimization algorithm based on merging the equivalent states, this method could further reduced the number of NFA states while accepting the same languages.

Key words:  non-deterministic finite automata; preorder relation; state merging; minimization