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

Issues Regarding ε in Formal Language and Automata Theory

作　　者：陈文宇[1] 王晓斌[1] 程小鸥[1] 孙世新[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都610054

出　　处：《计算机科学》2010年第1期243-244,264,共3页Computer Science

基　　金：863计划(2006AA01Z174)资助

摘　　要：讨论了形式语言与自动机理论中关于空串ε的一些问题。分析了ε产生式对文法和语言分类的影响;从文法和有限状态自动机的角度讨论了开始符号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.

关 键 词：ε句子 ε产生式 ε状态转换函数 带ε动作的有限状态自动机 

分 类 号：TP301.2[自动化与计算机技术—计算机系统结构]