有限自动机的确定化算法子集法问题探析

The Probe on the Subset Method Problems of Finite Automata Deterministic Algorithm

子集法是目前普遍采用的确定化NFA为DFA的方法,但在子集法存在两处疑难:一是NFA M的状态子集I的a弧转换集合Ia的定义与解释;二是确定化过程中先对NFA做改造的必要性以及条件。

The subset method is a popularly adopted method for the transition from non-deterministic finite au- tomata to deterministic finite automata, howeuer it faces two problems. One is the definition and explanation of a-arc transformation set Ia of NFA＇ s state subset I. The other is the necessity and conditions of reforming NFA in the process of its determination.