第3、第4周内容介绍

1、第3、第4周内容介绍理论计算机科学基础1理论计算机科学基础2第3、第4周内容提要上下文无关语言上下文无关文法(CFG)歧义性乔姆斯基范式下推自动机(PDA)PDA与CFG的等价性泵引理理论计算机科学基础3与第1、第2周内容的对比正则语言有穷自动机正则表达式 (表示正则语言)泵引理 (证明非正则语言)应用上下文无关语言上下文无关文法下推自动机泵引理应用 (递归结构,人类语言, 程序设计语言,自动处理)两个上下文无关文法的例子理论计算机科学基础4理论计算机科学基础5上下文无关文法的例子文法G1: A 0A1 A B B # 理论计算机科学基础6产生式的例子文法G1: A 0A1 A B B #产生

2、式(替换规则): A0A1, AB, B#理论计算机科学基础7变元的例子文法G1: A 0A1 A B B #变元(非终结符): A, B理论计算机科学基础8终结符的例子文法G1: A 0A1 A B B #终结符: 0,1, # 理论计算机科学基础9初始符的例子文法G1: A 0A1 A B B #初始符: A 理论计算机科学基础10一步派生的例子文法G1: A 0A1 A B B #派生: A理论计算机科学基础11一步派生的例子文法G1: A 0A1 A B B #派生: A 0A1理论计算机科学基础12一步派生的例子文法G1: A 0A1 A B B #派生: A 0A1 00A11理论

3、计算机科学基础13一步派生的例子文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111理论计算机科学基础14一步派生的例子文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111 000B111理论计算机科学基础15一步派生的例子文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111 000B111 000#111理论计算机科学基础16语法分析树的例子文法G1: A 0A1 A B B #派生: A语法分析树A理论计算机科学基础17语法分析树文法G1: A 0A1 A B B #派生: A 0A1语法分析树

4、AA01理论计算机科学基础18语法分析树文法G1: A 0A1 A B B #派生: A 0A1 00A11 语法分析树AAA0011理论计算机科学基础19语法分析树文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111 语法分析树AAAA000111理论计算机科学基础20语法分析树文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111 000B111语法分析树AAAAB000111理论计算机科学基础21语法分析树文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111 000B111 000#111语法分

5、析树AAAAB#000111理论计算机科学基础22生成的语言文法G1: A 0A1 A B B #G1生成的语言: L(G1)= 0n#1n | n0 AAAAB#000111理论计算机科学基础23产生式的缩写文法G1: A 0A1 A B B #缩写: G1: A 0A1 | B B #理论计算机科学基础24G2 | | | a_ | the_ boy_ | girl_ | flower_ touches_ | likes_ | sees_ with_理论计算机科学基础25G2a boy seesthe boy sees a flowera girl with a flower likes

6、the boy理论计算机科学基础26G2a_boy_sees_the_boy_sees_a_flower_a_girl_with_a_flower_likes_the_boy_理论计算机科学基础27G2 a_ a_boy_ a_boy_ a_boy_ a_boy_sees_上下文无关文法的定义理论计算机科学基础28理论计算机科学基础29CFG的形式定义定义3.1:上下文无关文法 G=(V,R,S), 1) V: 有穷变元集 2) : 有穷终结符集 3) R: 有穷规则集 ( 规则形如 Aw, w(V)* ) 4) SV: 初始变元理论计算机科学基础30CFG的形式定义一步生成(派生,推导):

7、uAvuwv (Aw是产生式)任意步生成(派生,推导):u*v: uu1u2ukv 或 u=v文法(生成)的语言: L(G)= w* | S*w 上下文无关语言(CFL): CFG生成的语言理论计算机科学基础31例G1 = ( A,B, 0,1,#, A0A1,AB,B#, A )理论计算机科学基础32例G2=( , , a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,_, , , , , , ,a_, the_,boy_,girl_,名词flower_,touches_, likes_,sees_,with_ , )理论计算机科学基础3

8、3例3.2G3=(S,a,b,R,S), 其中R为 S aSb | SS | S SS aSbS abS * abab. S aSb aaSbb * aaabbb. S aSb aSSb * aababb.L(G3)包含所有匹配的括号串 或空串. 理论计算机科学基础34例3.3G4=(V,R,), 其中 V=, = a, +, , (, ) , R为 + | | () | a 乘法比加法优先理论计算机科学基础35例3.3(续) a+aa的语法分析树 a+aa理论计算机科学基础36例3.3(续) (a+a)a的语法分析树+a)aa(设计上下文无关文法理论计算机科学基础37理论计算机科学基础38如

9、何设计CFG合并正则匹配递归理论计算机科学基础39合并CFG为 w|w=0n1n或w=1n0n,n0 设计CFG.理论计算机科学基础40合并CFG为 w|w=0n1n或w=1n0n,n0 设计CFG.为w|w=0n1n,n0设计CFG.为w|w=1n0n,n0设计CFG.理论计算机科学基础41合并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)理论计算机科学基础42合并CFG为 w|w=0n1n或w=1n0n,n0 设计CFG.为w|w

10、=0n1n,n0设计CFG.G1=(S1,0,1,S10S11,S1,S1)为w|w=1n0n,n0设计CFG.G2= (S2,0,1,S21S20,S2,S2)理论计算机科学基础43合并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)理论计算机科学基础44合并CFG一般情况: 增加 SS1 | S2 | Sk S

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

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

13、Rk, RiaRj, Ri定理定理: 正则语言都是 上下文无关语言.理论计算机科学基础53某些匹配0n1n理论计算机科学基础54某些匹配0n1nR0R1, R理论计算机科学基础55某些匹配0n1nR0R1, R0000011111理论计算机科学基础56某些匹配0n1nR0R1, R0000011111理论计算机科学基础57某些匹配0n1nR0R1, R0000011111wwR倒置: w=11010, wR=01011理论计算机科学基础58某些匹配wwR倒置: w=11010, wR=01011 可用上下文无关文法生成理论计算机科学基础59某些匹配wwR倒置: w=11010, wR=0101

14、1 可用上下文无关文法生成ww理论计算机科学基础60某些匹配wwR倒置: w=11010, wR=01011上下文无关ww非正则, 非上下文无关理论计算机科学基础61某些匹配wwR倒置: w=11010, wR=01011上下文无关ww非正则, 非上下文无关非ww理论计算机科学基础62某些匹配wwR倒置: w=11010, wR=01011上下文无关ww非正则, 非上下文无关非ww上下文无关理论计算机科学基础63递归结构(a+a)a(a+a)+a)a+a)aa(文法的歧义性理论计算机科学基础64理论计算机科学基础65歧义性G5: + | | () | a理论计算机科学基础66不同的分析树a+a

15、aa aa+理论计算机科学基础67不同的结构与不同的意义G2:the_girl_touches_the_boy_with_flower理论计算机科学基础68最左派生最左派生: 每一步都替换最左边的变元理论计算机科学基础69最左派生的例子 + a+ a+ a+a a+aa理论计算机科学基础70两个不同的最左派生 + a+ a+ a+a a+aa + a+ a+a a+aa理论计算机科学基础71歧义性地产生最左派生: 每一步都替换最左边的变元歧义地产生: 有两个不同的最左派生理论计算机科学基础72歧义文法最左派生: 每一步都替换最左边的变元歧义地产生: 有两个不同的最左派生歧义文法: 文法歧义地产

16、生某个串理论计算机科学基础73固有歧义性最左派生: 每一步都替换最左边的变元歧义地产生: 有两个不同的最左派生歧义文法: 文法歧义地产生某个串固有歧义语言: 只能用歧义文法产生理论计算机科学基础74固有歧义语言的例子固有歧义语言: 只能用歧义文法产生例: 0i1j2k | i=j 或 j=k 0n1n2m | n,m0 0m1n2n | n,m0 0n1n2n只能歧义地产生理论计算机科学基础75歧义性与非确定性固有歧义性 (Inherent Ambiguity)非确定性 (Nondeterminism)乔姆斯基范式的定义理论计算机科学基础76理论计算机科学基础77乔姆斯基范式(CNF)CNF:

17、 只允许如下形式的规则: SABCAa其中A,B,C是任意变元B,C不是初始变元 (初始变元不能在右方出现) a是任意终结符求乔姆斯基范式的算法理论计算机科学基础78理论计算机科学基础79乔姆斯基范式(CNF)等价: 两个文法生成同样语言定理3.6: 任何CFG都有 等价的CNF.理论计算机科学基础80定理3.6定理3.6: 任何CFG都有 等价的CNF.证明思路: 下列算法：1) 添加新的初始变元2) 处理A (规则)3) 处理AB (单一规则)4) 处理Au1u2uk (k3)5) 处理Aaiaj, AaiB, ABai理论计算机科学基础81添加新初始变元1) 添加新初始变元S0和规则 S

18、0S, 其中S是旧初始变元.理论计算机科学基础82处理规则2) 考虑所有规则. 若A不是初始变元,则删除A, 以各种可能的方式删除其他规则右边的A,添加新的规则,例如 由BuAv添加Buv 由BuAvAw添加BuvAw | uAvw | uvw 由BA添加B (除非已删除过B)直到删除所有规则(S0除外)为止.理论计算机科学基础83处理单一规则3) 处理所有单一规则. 删除AB, 若有规则Bu, 则添加规则Au, 除非Au是已删除过的单一规则. 重复上述步骤, 直到删除所有单一规则为止. 理论计算机科学基础84处理Au1u2uk规则4) 把每一条规则Au1u2uk换成 Au1A1 A1u2A2

19、 A2u3A3 Ak-2uk-1uk (k3)理论计算机科学基础85处理终结符5) 对每个终结符ai， 引入变元Ui和规则Uiai. 把Aaiaj换成AUiUj 把AaiB换成AUiB 把ABai换成ABui可以证明，这样求出的是等价的乔姆斯基范式 ， 定理3.6证明完毕。求乔姆斯基范式的例子理论计算机科学基础86理论计算机科学基础87例3.7 G6: S ASA | aB, A B | S B b | 求等价CNF.理论计算机科学基础88例3.7(1)G6: S ASA | aB, A B | S B b | (1) S0 S S ASA | aB A B | S B b | 理论计算机科学

20、基础89例3.7(2a)(2a) S0 S S ASA | aB A B | S B b | 理论计算机科学基础90例3.7(2a)(2a) S0 S S ASA | aB | a A B | S | B b理论计算机科学基础91例3.7(2b)(2b) S0 S S ASA | aB | a A B | S | B b理论计算机科学基础92例3.7(2b)(2b) S0 S S ASA | aB | a | SA | AS | S A B | S B b理论计算机科学基础93例3.7(3a)(3a) S0 S S ASA | aB | a | SA | AS | S A B | S B b理

21、论计算机科学基础94例3.7(3a)(3a) S0 S S ASA | aB | a | SA | AS A B | S B b理论计算机科学基础95例3.7(3b)(3b) S0 S S ASA | aB | a | SA | AS A B | S B b理论计算机科学基础96例3.7(3b)(3b) S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A B | S B b理论计算机科学基础97例3.7(3c)(3c) S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A B | S B

22、b理论计算机科学基础98例3.7(3c)(3c) S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A S | b B b理论计算机科学基础99例3.7(3d)(3d) S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A S | b B b理论计算机科学基础100例3.7(3d)(3d) S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A b | ASA | aB | a | SA | AS B b理论计算机科学基础101例3.7(4)

23、(4) S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A b | ASA | aB | a | SA | AS B b理论计算机科学基础102例3.7(4)(4) S0 AA1 | aB | a | SA | AS S AA2 | aB | a | SA | AS A b | AA3 | aB | a | SA | AS B b A1 SA A2 SA A3 SA理论计算机科学基础103例3.7(4)(4) S0 AA1 | aB | a | SA | AS S AA1 | aB | a | SA | AS A b | AA1 | aB

24、| a | SA | AS B b A1 SA理论计算机科学基础104例3.7(5)(5) S0 AA1 | aB | a | SA | AS S AA1 | aB | a | SA | AS A b | AA1 | aB | a | SA | AS B b A1 SA理论计算机科学基础105例3.7(5)-完成(5) S0 AA1 | UB | a | SA | AS S AA1 | UB | a | SA | AS A b | AA1 | UB | a | SA | AS B b A1 SA U a 下推自动机的例子理论计算机科学基础106理论计算机科学基础107下推自动机(PDA)状态控

25、制器单向只读输入带0 0 1 1 1单向只读头栈$理论计算机科学基础108下推自动机(PDA)状态控制器单向只读输入带0 0 1 1 1单向只读头$栈$理论计算机科学基础109下推自动机(PDA)状态控制器单向只读输入带0 0 1 1 1单向只读头$栈$0理论计算机科学基础110下推自动机(PDA)状态控制器单向只读输入带0 0 1 1 1单向只读头$栈$00理论计算机科学基础111下推自动机(PDA)状态控制器单向只读输入带0 0 1 1 1单向只读头$栈$0理论计算机科学基础112下推自动机(PDA)状态控制器单向只读输入带0 0 1 1 1单向只读头$栈$理论计算机科学基础113下推自动

26、机(PDA)状态控制器单向只读输入带0 0 1 1 1单向只读头$栈$理论计算机科学基础114例 0n1n | n0 读输入中的符号,每读一个0,把一个0推入栈一旦看见1之后, 就每读一个1,把一个0弹出栈l如果当读完输入串时, 恰好排空栈中的0, 则接受; 否则拒绝l如果在还有1没有读完时, 栈就排空, 则拒绝l如果在1读完时, 栈中还有0, 则拒绝l如果0出现在1的后面, 则拒绝理论计算机科学基础115非确定性 0n1n | n0 确定型PDA, 即DPDA anbncm, anbmcn | m,n0 固有歧义非确定型PDA, 即NPDA, 简称PDA一般说PDA指的是非确定型PDA下推自

27、动机的定义理论计算机科学基础116理论计算机科学基础117PDA的形式定义定义3.8: PDA M=(Q,q0,F), 其中1) Q: 有穷状态集2) : 输入字母表, =3) : 栈字母表, =4) : QP(Q), 转移函数5) q0Q: 初始状态6) FQ: 接受状态(终结状态)集理论计算机科学基础118PDA计算的形式定义M=(Q,q0,F); 输入w=w1w2wm, wi计算: 状态-栈符号串序列 (r0,s0), (r1,s1), (rm ,sm), 其中 riQ, si*, 满足 1) (r0,s0)=(q0,); 2) (ri+1,b)(ri,wi+1,a); 其中 si=at; si+1=bt, a,b, t*理论计算机科学基础119PDA计算的形式定义接受计算:3) rmF; (或者同时要求sm=)M接受w: M对输入w存在接受计算M(识别,接受)的语言: L(M) = x | M接受x 下推自动机的例子理论计算机科学基础120理论计算机