形式语言与自动机中关于ε的一些问题

Issues Regarding ε in Formal Language and Automata Theory

讨论了形式语言与自动机理论中关于空串ε的一些问题。分析了ε产生式对文法和语言分类的影响;从文法和有限状态自动机的角度讨论了开始符号S和开始状态q0的作用;提出了语言增加或减少ε句子的简单方法;研究了ε-NFA的ε状态转换函数的本质;提出了ε-NFA转换为NFA的新方法,即先将ε-NFA转换为文法形式,消除ε产生式和单产生式后得到正则文法,再将正则文法转换为NFA。并用实际例子进行了验证。

The paper discussed some issues regarding blank string e in the formal language and automata theory. After analysis of the influence of production e on grammar and language classification, the paper discussed the effect of starting symbol S and the starting state q0 from the perspective of grammer and infinite state and proposed a simple method to increase language or decrease sentence ε. The paper also proposed a new method to transit ε-NFA to NFA after studying the essence of ε state transition function of ε-NFA. The method is： first transit ε-NFA to formal grammar and eliminate production ε and single production. After that, regular grammar was obtained. Then transited regular grammar to NFA. Examples were given to support the discussion.