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

【Abstract】 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.更多还原