编译原理2.2自动机理论讲述必威体育精装版.ppt

* 例5：L(M) 如下图，求L(R) . - + abb bb ab ba a,b a ? 解： ? - + abb bb abba a,b a * abba|abb|bb + a,b - a a*(abba|abb|bb)(a|b)* + - 所以 L(R) = a*(abba|abb|bb)(a|b)* 注：abba+abb+bb 不能把bb提取出来 * 2、L(R) ?NFA，从正规式R构造NFA 由正规式V直接形成拓广的FA状态图。构造∑上的NFA M’，使得L(M’)=L(V); 方法如下： * Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA ai 1) 若V是ε或∑上的字符ai , 则 2) 若1）不成立，则V具有V1|V2，V1?V2，(V1)*形式 ，按照替换规则二分解V； 3） 对新产生的弧标记重复1）、2），直到没有新的 弧和结产生为止。得到V相应的M’，且L(M’)=L(v). X Y X Y ε * Ch2 形式语言自动机理论基础 2.3 正规式与自动机 2.3.2 正规式与FA R1 R1|R2 A B R2 A B 替换为 R1* A B ε A C ε B 替换为 R1 A C R2 B R1R2 A B 替换为 R1 替换规则二 (1) ⑵ ⑶ * 例1：L(R) =(a|b)*abb，构造NFA使L(N)=L(R) 解： x y ? (a|b)* abb x ? y abb ? ? a,b x ? y abb ? ? a b ? x ? y ? ? a b a b b * 例： L(R) =(a|b)*(aa|bb)(a|b)* 构造L(M)使与L(R) 等价。 * x y ? (a+b)*(aa+bb)(a+b)* x y ? (a+b)* aa+bb (a+b)* x y ? aa bb a,b a,b ? ? * x y ? a b ? ? a a a b b b * 八、正规文法和有穷自动机的等价性 采用下面的规则可以从正规文法G直接构造一个有穷 　自动机NFA　M；使得L（M）＝L（G）： M的字母表与G的终结符集相同 为G中的每个非终结符生成M的一个状态，G的开始符S是开始状态S 增加一个新状态Z，作为NFA的终态 对G中的形如A→ tB的规则（其中t为终结符或?，A和B为 　非终结符的产生式），构造M的一个转换函数f(A,t)=B 对G中形如A→ t的产生式，构造M的一个转换函数f(A,t)=Z * [例2-6] 已知正规文法G3＝({S，A，B}，{a，b，c}，P，S)，其中P内包含以下产生式： 根据上述转换方法，与G3等价的FA M为： 其中δ函数的定义式为： * 例2：与文法G［S］等价的NFA　M如图4.11 G[S]: S →a A S →bB S →ε A →aB A →bA B →aS B →bA B →ε * 有穷自动机转换成等价的正规文法： 对转换函数f(A,t)=B,可写一产生式：A → tB 对可接受状态Z，增加一产生式：Z → ε 有穷自动机的初态对应文法开始符 有穷自动机的字母表为文法的终结符集 * 例3：给出与图4.12的NFA等价的正规文法G G＝（｛A，B，C，D｝，｛a，b}，P，A），其中P为： A → a B C → ε A → bD D → aB B → bC D → bD C → aA D → ε C → bD * 本章小结 词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。 本章讲述了词法分析程序设计原则，并介绍了分别作为正规集的描述机制和识别机制的正规式和有穷动机。 正规表达式在编译原理中的作用特别大，要将其概念和用法掌握。 重点：1、NFA的确定化；DFA的化简 2、正规文法、正规式、NFA、DFA之间相互变换方法 * 课堂习题与练习： 1、确定的有穷自动机是一个 （1） ，通常表示为 （2） 。 答案：（1）五元组 （2）DFA=（K，Σ，f，S，Z） 2、 这样一些语言，它们能被确定的有穷自动机识别