自动机到正规表达式的重构方法研究

Research on Reconstruction Method from Automaton to Regular Ex pression

自动机理论是编译程序中单词识别的基本理论。论文分析了自动机与正规表达式等价性定理,指出了从确定有限自动机到正规表达式重构规则中存在的问题,给出了一个包含多个结点所组成回路的有限自动机到正规表达式的重构定理,并通过实例对于该定理所阐明的方法的运用进行了详细的讨论。

Automaton theory is a basic theory of compile routine for identifying words.This paper analyses the equivalence theorem of automaton and regular expression,and indicates the problem existing in the reconstruction rule from certain finite automaton to regular expression.A reconstruction theorem from finite automaton including many nodes in the cycle to regular expression is given in the paper,and the application of the method clarified in this theorem is discussed in detail.