第三章词法分析2自动机.ppt

* r= ? 2. 对Σ上的正规式r构造Σ上的NFA M使得L(M)=L(r) ? a qf q0 q0 q0 qf qf q0 r=? r=a * r=r1|r2 f0 q1 f1 M1 q0 q2 f2 M2 ? ? ? ? L(r)=L(M1) ∪L(M2) 2续.对Σ上的正规式r构造Σ上的NFA M使得L(M)=L(r) * r=r1r2 L(r)=L(M1) L(M2) q1 f1 M1 q2 M2 ? f2 2续.对Σ上的正规式r构造Σ上的NFA M使得L(M)=L(r) * r=r1* L(r)=L(M1) * f0 q1 f1 M1 q0 ? ε ? ? 2续.对Σ上的正规式r构造Σ上的NFA M使得L(M)=L(r) * 例：从正规式到 NFA ab+|ab*|b* 2 1 ab+|ab*|b* 2 1 ab+ ab* b* 2 1 a 3 3 3 b b b b a ? ? ? * 例：从正规式到 NFA (续) ab+|ab*|b* 2 1 (ab|a|?)b* 2 1 ab a ? b b 2 1 a a ? 3 ? b 2 1 a a ? 3 b 正规文法??正规式 一个正规语言可以由正规文法定义，也可以由正 规式定义。 b) 对任一个正规文法，存在一个定义同一个语言的 正规式；反之，对每个正规式，存在一个生成同 一语言的正规文法。 c) 有些正规语言很容易用文法定义，有些更容易用 正规式定义。 １、正规式?正规文法 规则: 将∑上的一个正规式转换成文法G=(VN,VT, S, P) (1)令VT=∑; (2)确定产生式和VN的元素用如下办法: ①对任何正规式r, 选择S∈VN, 生成产生式S?ｒ，且定Ｓ为开始符号． ②若ｘ，ｙ均为正规式，则： 对形如Ａ?ｘｙ的产生式，重写成Ａ?ｘＢ，Ｂ?ｙ， Ｂ∈ＶＮ且为新选; 对形如Ａ?ｘ*ｙ的产生式，重写成Ａ?ｘA，Ａ?ｙ; 对形如Ａ?ｘ｜ｙ的产生式，重写成Ａ?ｘ，A?ｙ， Ｂ∈ＶＮ且为新选. 例题：已知正规式Ｒ＝ａ（ａ｜ｄ）*，将其转换成相 　　应的正规文法。 （１）S?ａ（ａ｜ｄ）* （２）Ｓ?ａＡ Ａ?（ａ｜ｄ）* （３）Ｓ?ａＡ Ａ?（ａ｜ｄ）A Ａ? ? （４）Ｓ?ａＡ Ａ?ａA Ａ?ｄA Ａ? ? 即Ｓ?ａＡ Ａ?ａA｜ｄA｜? ２、正规文法?正规式 转换规则如下: 　（１）Ａ?ｘＢ，Ｂ?ｙ Ａ＝ｘｙ 　（２）Ａ?ｘＡ｜ｙ Ａ?ｘ*ｙ 　（３）Ａ?ｘ，Ａ?ｙ Ａ?ｘ｜ｙ 不断利用上述规则变换，最后只剩下一个开始符号定义的产生式，且该产生式的右部不含非终结符。 即 Ｓ?ａＡ Ａ?ａA Ａ?ｄA Ａ?? ２、正规文法?正规式 转换规则如下: 　（１）Ａ?ｘＢ，Ｂ?ｙ Ａ＝ｘｙ 　（２）Ａ?ｘＡ｜ｙ Ａ?ｘ*ｙ 　（３）Ａ?ｘ，Ａ?ｙ Ａ?ｘ｜ｙ 不断利用上述规则变换，最后只剩下一个开始符号定义的产生式，且该产生式的右部不含非终结符。 例题：已知文法Ｇ：Ｓ?ａＡ，Ｓ?ａ 　　Ａ?ａＡ，Ａ?ｄＡ，Ａ?ａ，Ａ?ｄ 　　求其对应的正规式？ 分析：Ｓ＝ａＡ｜ａ Ａ＝（ａＡ｜ｄＡ）｜（ａ｜ｄ） ? 　 Ｓ＝ａＡ｜ａ 　　　Ａ＝（ａ｜ｄ）Ａ｜（ａ｜ｄ） ? Ｓ＝ａＡ｜ａ Ａ＝（ａ｜ｄ）＊（ａ｜ｄ）＝（ａ｜ｄ）+ ? Ｓ＝ａ（ａ｜ｄ）+｜ａ ? Ｓ＝ａ［（ａ｜ｄ）+｜? ］＝ａ（ａ｜ｄ）＊ 转换规则如下: 　（１）Ａ?ｘＢ，Ｂ?ｙ Ａ＝ｘｙ 　（２）Ａ?ｘＡ｜ｙ Ａ?ｘ*ｙ 　（３）Ａ?ｘ，Ａ?ｙ Ａ?ｘ｜ｙ * 结论 正规文法、正规式、确定有限自动机、非确定有限自动机在接受语言能力上等价。 正规式 ＮＦＡ ＤＦＡ 最小ＤＦＡ 正规文法 ⑤ 　　① 　② 　　　　③ 　④ ⑥　 * 一个DFA M的化简是指： 寻找一个状态数比M少的DFA M’，使得L(M)=L(M’)。 M的两个状态s和t是等价的：当且仅当分别从二者出发至终态均能够读出同一字。 M的两个状态s和t是可区别的：当且仅当二者不等价。 一个DFA M的状态最少化过程旨在将M的状态集分割成一些不相交的子集，使得任何不同的两个子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选出一个代表，同时消去其它等价状态。 3.3.6 确定有限自动机的化简 * 设DFA M = (S，?，δ，q0，F) 对不同的状态q１， q２∈Q 和每个ω∈?*，如果有 (q１，ω)=* (q，ε) 必有 (q２，ω)=* (q，ε) 且q∈F， 则称q１与q２状态