有穷自动机计算中数据结构的设计

尽管邻接矩阵是有穷自动机的一种常用存储方法,但是,邻接矩阵并不适合存储所有类型的有穷自动机.原因是两个状态间可能有两条以上同方向的弧,而邻接矩阵只能记录两个状态间存在的一条弧.所以,有穷自动机的存储结构最好采用邻接链表来存储.将此数据结构应用于NFA转换为DFA的计算,将传统的子集法中状态转换矩阵,由三维数组降低为二维数组.

Data structure designed for finite automata computation

Although the adjacency matrix was a storage structure of finite automaton in common use, it was not proper to store all kinds of finite automata. Perhaps existing two arcs above in the same direction between two states, adjacency matrix could only record one of them. So the storage structure of finite automaton should the choosed adjacency lists. We use it to realize the computation of transition from NFA to DFA by reducing the number of the transition matrix dimensions from a three-dimensional array in traditional subset approach to a two-dimensional array in the new algorithm.