第二章形式语言与自动机形式文法内容回顾语言的有穷表示有两个途经：生成方式识别方式一些关键概念0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法（上下文有关文法CSG）：产生式的形式为α1Aα2→α1βα2，即只有A出现在α1和α2的上下文中时，才允许β取代A。其识别系统是线性有界自动机。2型文法（上下文无关文法CFG）：产生式的形式为A→β，β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合PartII自动机正规文法与正规式正规式定义（正规式和它所表示的正规集）：设字母表为，辅助字母表`={，，，，，，}。1.和都是上的正规式，它们所表示的正规集分别为{}和{}；2.任何a，a是上的一个正规式，它所表示的正规集为{a}；3.假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1))。4.仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。正规式中的符号例子正规式的等价正规文法和正规式正规文法和正规式对上的正规式r,存在一个RG=(VN,VT,P,S)：L(G)=L(r)例r=a(ad)例标识符定义的转换引入idid→let(let|dig)*引入rid消除连接rid→(let|dig)*→ε|(let|dig)BB→(let|dig)BB→ε正规文法和正规式对G=(VN,VT,P,S),存在一个=VT上的正规式r:L(r)=L(G)正规文法和正规式例：请指出下列哪些字符串包含在正规式ab*c*(a|b)c所对应的正规集合中：acacacbbcabbcacabcacc作业