3.3设计上下文无关文法

1、设计上下文无关文法理论计算机科学基础1理论计算机科学基础2如何设计CFG合并正则匹配递归理论计算机科学基础3合并CFG为 w|w=0n1n或w=1n0n,n0 设计CFG.理论计算机科学基础4合并CFG为 w|w=0n1n或w=1n0n,n0 设计CFG.为w|w=0n1n,n0设计CFG.为w|w=1n0n,n0设计CFG.理论计算机科学基础5合并CFG为 w|w=0n1n或w=1n0n,n0 设计CFG.为w|w=0n1n,n0设计CFG.G1=(S,0,1,S0S1,S,S)为w|w=1n0n,n0设计CFG.G2=(S,0,1,S1S0,S,S)理论计算机科学基础6合并CFG为 w|w

2、=0n1n或w=1n0n,n0 设计CFG.为w|w=0n1n,n0设计CFG.G1=(S1,0,1,S10S11,S1,S1)为w|w=1n0n,n0设计CFG.G2= (S2,0,1,S21S20,S2,S2)理论计算机科学基础7合并CFG为 w|w=0n1n或w=1n0n,n0 设计CFG.为w|w=0n1n,n0设计CFG.G1=(S1,0,1,S10S11,S1,S1)为w|w=1n0n,n0设计CFG.G2= (S2,0,1,S21S20,S2,S2)G=(S,S1,S2,0,1, SS1, SS2, S10S11, S1, S21S20, S2,S)理论计算机科学基础8合并CFG

3、一般情况: 增加 SS1 | S2 | Sk S是新的初始变元S1, S2, , Sk 是原来的初始变元理论计算机科学基础9合并CFG一般情况: 增加 SS1 | S2 | Sk S是新的初始变元S1, S2, , Sk 是原来的初始变元定理: CFL对并运算封闭. # 理论计算机科学基础10正则语言为正则语言设计CFG.理论计算机科学基础11正则语言为正则语言设计CFG.把DFA转换成等价的CFG理论计算机科学基础12正则语言为正则语言设计CFG.把DFA转换成等价的CFG设DFA M=(Q,q0,F)则CFG G=(V,R,R0)理论计算机科学基础13正则语言为正则语言设计CFG.把DFA

4、转换成等价的CFG设DFA M=(Q,q0,F)Q=q0,q1,qk,则CFG G=(V,R,R0)V=R0,R1,Rk,理论计算机科学基础14正则语言为正则语言设计CFG.把DFA转换成等价的CFG设DFA M=(Q,q0,F)(qi,a)=qj,则CFG G=(V,R,R0)RiaRj,理论计算机科学基础15正则语言为正则语言设计CFG.把DFA转换成等价的CFG设DFA M=(Q,q0,F)qiF则CFG G=(V,R,R0)Ri理论计算机科学基础16正则语言为正则语言设计CFG.把DFA转换成等价的CFG设DFA M=(Q,q0,F)Q=q0,q1,qk, (qi,a)=qj, qiF

5、则CFG G=(V,R,R0)V=R0,R1,Rk, RiaRj, Ri定理: 正则语言都是 上下文无关语言.理论计算机科学基础17某些匹配0n1n理论计算机科学基础18某些匹配0n1nR0R1, R理论计算机科学基础19某些匹配0n1nR0R1, R 理论计算机科学基础20某些匹配0n1nR0R1, R 理论计算机科学基础21某些匹配0n1nR0R1, R wwR倒置: w=11010, wR=01011理论计算机科学基础22某些匹配wwR倒置: w=11010, wR=01011 可用上下文无关文法生成理论计算机科学基础23某些匹配wwR倒置: w=11010, wR=01011 可用上下文无关文法生成ww理论计算机科学基础24某些匹配wwR倒置: w=11010, wR=01011上下文无关ww非正则, 非上下文无关理论计算机科学基础25某些匹配wwR倒置: w=11010, wR=01011上下文无关ww非正则, 非上下文无关非ww理论计算机科学基础26某些匹配