有限自动机的半环方法

The Method of Semirings of Finite Automata

文章利用半环方法来讨论有限自动机.首先,利用线性代数基础给出半环上有限自动机的概念;然后,证明了半环上的有限自动机与不确定的有限状态自动机识别语言的一致性.从数学的角度看该方法使得有限自动机的讨论更加简洁.

In this note the finite automaton is discussed by the method of semirings. Firstly,the definition of the finite automaton of semirings based on linear algebra is given. Then the identity of the acceptance of languages is proved between the finite automaton of semirings and the non-deterministic finite automaton. The method makes the discussion of the finite automaton more concise from the mathematical point of view.