计算理论导引-2-上下文无关文法ppt课件.ppt

《计算理论导引-2-上下文无关文法ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算理论导引-2-上下文无关文法ppt课件.ppt（57页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。计算理论1严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。主要内容主要内容2.1 上下文无关文法概述上下文无关文法概述2.1.1 上下文无关文法的形式化定义上下文无关文法的形式化定义2.1.2 上下文无关文法举例上下文无关文法举例2.1.3 设计上下文无关文法设计上下文无关文法2.1.4 歧义性歧义性2.1.5 乔姆斯基范式乔姆斯基范式2.2 下推自动机下推自动机2.2.1 下推自动机的形式化定义下推自动机的形式化定义2

2、.2.2 下推自动机举例下推自动机举例2.2.1 与上下文无关文法的等价性与上下文无关文法的等价性2.3 非上下文无关语言非上下文无关语言2严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。上下文无关文法(CFG)概述A 0A1A BB#替换规则替换规则变量变量(Variables)A,B终止符终止符(Terminals)0,1,#起始变元起始变元(Start Variable)A箭头的左侧只有一个变量替换规则又称为替换规则又称为产生式产生式3严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各

3、类违纪行为或突发事件。如何利用 CFG 产生字符串A 0A1A BA#q获取一个字符串的获取一个字符串的替换过程替换过程叫叫派生派生。q例如字符串例如字符串 000#111 的过程如下：的过程如下：A 0A1 00A11 000A111 000B111 000#111(1)(1)写下起始变元写下起始变元写下起始变元写下起始变元第一条规则左边的变元。第一条规则左边的变元。第一条规则左边的变元。第一条规则左边的变元。(2)(2)取一个已写下的变元，并找到以该变元开始取一个已写下的变元，并找到以该变元开始取一个已写下的变元，并找到以该变元开始取一个已写下的变元，并找到以该变元开始的规则，把这个变元替

4、换成规则右边的字符的规则，把这个变元替换成规则右边的字符的规则，把这个变元替换成规则右边的字符的规则，把这个变元替换成规则右边的字符串。串。串。串。(3)(3)重复步骤重复步骤重复步骤重复步骤2 2，直到写下的字符串没有变元。，直到写下的字符串没有变元。，直到写下的字符串没有变元。，直到写下的字符串没有变元。4严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。如何利用 CFG 产生字符串A 0A1A BA#可以用可以用语法生成树语法生成树形象地表示派生过程。形象地表示派生过程。AAAB#000111A5严格执行突发事件上报制度、校外

5、活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。文法的语言A 0A1A BA#q文法文法 G1 可以产生的字符串包括：可以产生的字符串包括：#,0#1,00#11,000#111,q用文法用文法 生成的所有字符串的集合称为生成的所有字符串的集合称为文法文法的语言。的语言。qL(G1)表示文法表示文法 G1 产生的语言。产生的语言。L(G1)=0n#1n|n 0 q用上下文无关文法产生的语言叫用上下文无关文法产生的语言叫上下文无上下文无关语言关语言。q文法文法 G1 的简写：的简写：A 0A1|BB#6严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做

6、到及时发现、制止、汇报并处理各类违纪行为或突发事件。上下文无关文法的形式化定义定义定义定义定义2.12.1上下文无关文法是一个上下文无关文法是一个 4 元组元组(V,R,S)，且，且(1)V 是一个有穷集合，称为是一个有穷集合，称为变元集变元集。(2)是一个与是一个与 V 不相交的有穷集合，称为不相交的有穷集合，称为终结符终结符集集。(3)R 是一个有穷是一个有穷规则集规则集，每条规则由一个变元和，每条规则由一个变元和一个由变元及终结符组成的字符串构成。一个由变元及终结符组成的字符串构成。(4)S V 是是起始变元起始变元。7严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发

7、现、制止、汇报并处理各类违纪行为或突发事件。CFG的术语q假设假设 u 与与 v 由变元及终结符构成的字符串，由变元及终结符构成的字符串，Aw 是文法的是文法的一条规则，称一条规则，称 uAv 生成生成 uwv，记作，记作uAv uwv。q如果如果 u=v，或者存在，或者存在 u1,u2,uk,k 0 使得使得u u1 u2 uk v，则称，则称 u 派生派生 v，记作，记作 u*v。q文法文法 G=(V,T,R,S)的语言为的语言为 L(G)=w T*|S w 8严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。上下文无关文法举例

8、例例2.1 考虑文法考虑文法 G=(S,a,b,R,S)，其中规则集，其中规则集 R 为：为：S aSb|SS|。该文法生成该文法生成 abab，aaabbb，aababb，如果将如果将 a 看作看作(，将，将 b 看作看作)，L(G)是所有正常嵌套的括号字符串构成的语言。是所有正常嵌套的括号字符串构成的语言。9严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。设计上下文无关文法q设计如下语言的上下文无关文法设计如下语言的上下文无关文法0n1n|n 01n0n|n 0 0n1n|n 01n0n|n 0q设计技巧设计技巧化繁为简，利用

9、正则，考察子串，利用递归。化繁为简，利用正则，考察子串，利用递归。10严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。设计上下文无关文法qCFG for L1=0n1n|n 0S 0S1|qCFG for L2=1n0n|n 0S 1S0|qCFG for L1L2S S1|S2S1 0S11|S2 1S20|qCFG for L3=02n13n|n 0?S 00S111|11严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。上下文无关文法与正则语言任何正则语言可以由任

10、何正则语言可以由 CFG 描述。描述。如果如果 (qi,a)=qj，则增加规则，则增加规则 Vi aVj如果如果 qi 是接受状态，则增加规则是接受状态，则增加规则 Vi 如果如果 q0 是起始状态，则是起始状态，则 V0 是起始变元。是起始变元。q0q110start01DFACFGG=(V0,V1,0,1,R,V0)V0 0V0|1V1|V1 1V1|0V012严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。最左派生q对于文法对于文法 G 中的一个字符串中的一个字符串 w 的派生，如果在每一步都是的派生，如果在每一步都是替换左

11、边剩下的变元替换左边剩下的变元，则称这个派生是，则称这个派生是最左派生最左派生。q例如例如G=(S,(,),R,S)，其中规则为，其中规则为 S (S)|SS|S SS (S)S ()S ()(S)()()S SS S(S)(S)(S)()(S)()()13严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。歧义性q一个串可能有两个甚至更多的最左派生。一个串可能有两个甚至更多的最左派生。q例如例如 CFG G=(S,+,*,a,R,S)，其中规则为，其中规则为 S S+S|S*S|a产生串产生串 a+a*aS S+S a+S a+S*

12、S a+a*S a+a*a S S*S S+S*S a+S*S a+a*S a+a*a SSSSS+aaaxSSSSSx+aaa14严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。歧义性定义定义定义定义2.42.4如果字符串如果字符串 w 在上下文无关文法在上下文无关文法 G 中有中有两个或两个或两个以上不同的最左派生两个以上不同的最左派生，则称，则称 G 歧义地歧义地(ambiguously)产生字符串产生字符串 w，如果文法，如果文法 G 歧义歧义地产生某个字符串，则称地产生某个字符串，则称 G 是是歧义的歧义的。某些上下文无

13、关语言只能用歧义文法产生，这样某些上下文无关语言只能用歧义文法产生，这样的语言是的语言是固有二义的固有二义的。15严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。乔姆斯基范式定义定义定义定义2.52.5称一个上下文无关文法是为称一个上下文无关文法是为乔姆斯基范式乔姆斯基范式(Chomsky normal form)，如果它的每一个规则具有如下形式：，如果它的每一个规则具有如下形式：A BCA a其中其中 a 是任意的终结符，是任意的终结符，A、B 和和 C 是任意的变元，是任意的变元，且且 B 和和 C 不能同时是起始变元。此外，

14、允许规则不能同时是起始变元。此外，允许规则S ，其中，其中 S 是起始变元。是起始变元。16严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。乔姆斯基范式定理定理定理定理2.62.6任一上下文无关语言都可以用一个乔姆斯基范式的上任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。下文无关文法产生。qStep 1:增加起始变元增加起始变元 S0 和规则和规则 S0 S,其中其中S是原来的起始是原来的起始变元。变元。qStep 2:考虑所有的考虑所有的 规则。规则。对于对于 A ,删去每个删去每个A都会产都会产生一个新规则。

15、生一个新规则。例如例如 R uAvAw R uAvw,R uvAw,R uvw17严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。乔姆斯基范式定理定理定理定理2.62.6任一上下文无关语言都可以用一个乔姆斯基范式的上任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。下文无关文法产生。qStep 3:考虑单一产生式考虑单一产生式A B。例如：例如：A B,B aC,B CC,则增加则增加A aC,A CC。qStep 4:考虑考虑A u1 u2 uk,其中其中 k 2且且ui 是变量或终结符。是变量或终结符。替换该规则

16、替换该规则A u1A1,A1 u2A2,A2 u3A3,Ak-2 uk-1uk18严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例题S ASA|aBA B|SB b|S0 SS ASA|aBA B|SB b|19严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例题qAfter that,we remove B S0 SS ASA|aBA B|SB b|S0 SS ASA|aB|aA B|S|B b Before removing B After removing B

17、 20严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例题qAfter that,we remove A S0 SS ASA|aB|aA B|S|B b Before removing A After removing A S0 SS ASA|aB|a|SA|AS|SA B|SB b 21严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例题qThen,we remove S S and S0 SAfter removing S S After removing S0

18、S S0 SS ASA|aB|a|SA|ASA B|SB b S0 ASA|aB|a|SA|ASS ASA|aB|a|SA|ASA B|SB b 22严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例题qThen,we remove A BBefore removing A B After removing A B S0 ASA|aB|a|SA|ASS ASA|aB|a|SA|ASA B|SB b S0 ASA|aB|a|SA|ASS ASA|aB|a|SA|ASA b|SB b 23严格执行突发事件上报制度、校外活动报批制度等相

19、关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例题qThen,we remove A SBefore removing A S After removing A S S0 ASA|aB|a|SA|ASS ASA|aB|a|SA|ASA b|SB b S0 ASA|aB|a|SA|ASS ASA|aB|a|SA|ASA b|ASA|aB|a|SA|ASB b 24严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例题qThen,we apply Step 4Before Step 4After Step 4 Gra

20、mmar is in CNFS0 ASA|aB|a|SA|ASS ASA|aB|a|SA|ASA b|ASA|aB|a|SA|ASB b S0 AA1|UB|a|SA|ASS AA1|UB|a|SA|ASA b|AA1|UB|a|SA|ASB b A1 SAU a25严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。主要内容主要内容2.1 上下文无关文法概述上下文无关文法概述2.1.1 上下文无关文法的形式化定义上下文无关文法的形式化定义2.1.2 上下文无关文法举例上下文无关文法举例2.1.3 设计上下文无关文法设计上下文无关文法

21、2.1.4 歧义性歧义性2.1.5 乔姆斯基范式乔姆斯基范式2.2 下推自动机下推自动机2.2.1 下推自动机的形式化定义下推自动机的形式化定义2.2.2 下推自动机举例下推自动机举例2.2.1 与上下文无关文法的等价性与上下文无关文法的等价性2.3 非上下文无关语言非上下文无关语言26严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。下推自动机考虑语言考虑语言 0n1n|n0 的识别装置的识别装置xyz$状态状态控制器控制器栈栈下推自动机下推自动机(pushdown automata)PDA=NFA+stack with unli

22、mited size确定型确定型 PDA 和非确定型和非确定型 PDA 的语言识别能力不相同的语言识别能力不相同。aabb27严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。下推自动机(PDA)的形式化定义定义定义定义定义2.82.8下推自动机是下推自动机是 6 元组元组(Q,q0,F)(1)Q 是一个有穷集合，称为是一个有穷集合，称为状态集状态集。(2)是一个有穷集合，称为是一个有穷集合，称为输入字母表输入字母表。(3)是一个有穷集合，称为是一个有穷集合，称为栈字母表栈字母表。(4):Q P(Q )是是转移函数转移函数，其中其中

23、 =,=(5)q0 Q是是起始状态起始状态。(6)F Q是是接受状态集接受状态集。PDA 的形式化定义没有提供检验空栈的直接手段。的形式化定义没有提供检验空栈的直接手段。约定约定 PDA 在开始时就把一个特殊符号在开始时就把一个特殊符号$放入栈中。放入栈中。28严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。PDA的计算过程PDA M=(Q,q0,F)接受输入串接受输入串 w，如果，如果能够把能够把 w 写成写成 w1w2wm，其中，其中 wi 存在状态序列存在状态序列 r0,r1,rmQ 存在存在 s0,s1,sm *满足下述满

24、足下述 3 个条件，字符串个条件，字符串si 是是 M 在计算的接受分支中的栈在计算的接受分支中的栈内容序列。内容序列。(1)r0=q0,s0=(2)对于对于 i=0,1,m-1,有有(ri+1,b)(ri,wi+1,a),其中其中 si=at,si+1=bt,a,b (3)rm F29严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。下推自动机举例例例2.9 描述识别语言描述识别语言 0n1n|n 0的的 PDA M。q1q2q3q4,$1,0 0,01,0 ,$qM=(q1,q2,q3,q4,0,1,0,$,q1,q1,q4),

25、q(q1,)=(q2,$),(q2,0,)=(q2,0)(q2,1,0)=(q3,),(q3,1,0)=(q3,)(q3,$)=(q4,),(q,x,y)=30严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。下推自动机举例例例2.10 构造识别语言构造识别语言 aibjck|i,j,k 0 且且 i=j 或或 i=k 的的 PDA M。q1q2q5q6,$a,a,$q7q3q4,$b,c,a ,c,b,a 31严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。下推自动机

26、举例例例2.11 构造识别语言构造识别语言 wwR|w 0,1*的的 PDA M。q1q2q3q4,$0,0 1,1 0,01,1,$32严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。PDA与上下文无关文法的等价性定理定理定理定理2.122.12一个语言是上下文无关的，当且仅当存在一台下推一个语言是上下文无关的，当且仅当存在一台下推自动机识别它。自动机识别它。引理引理引理引理2.132.13如果一个语言是上下文无关的，则存在一台下推自如果一个语言是上下文无关的，则存在一台下推自动机识别它。动机识别它。引理引理引理引理2.152.

27、15如果一个语言被一台下推自动机识别，则它是上下如果一个语言被一台下推自动机识别，则它是上下文无关的。文无关的。33严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。PDA与上下文无关文法的等价性引理引理引理引理2.132.13如果一个语言是上下文无关的，则存在一台下推自如果一个语言是上下文无关的，则存在一台下推自动机识别它。动机识别它。设设 A 是一个是一个 CFL，根据定义，存在一个，根据定义，存在一个 CFG G 产生它。产生它。如何把如何把 G 转换成一台等价的转换成一台等价的 PDA P。通通过过确确定定是是否否存存在在关

28、关于于输输入入 w 的的派派生生，当当 G 产产生生 w 时时，PDA P 接受这个输入。接受这个输入。设计设计 P，以确定是否有一系列使用，以确定是否有一系列使用 G 的规则替换。的规则替换。34严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。由CFG 构造 PDAP 的非形式化描述如下：的非形式化描述如下：(1)把标记符把标记符$和起始变元放入栈中。和起始变元放入栈中。(2)重复下述步骤：重复下述步骤：a)如果如果栈顶是变元栈顶是变元 A，则非确定地选择一个关于，则非确定地选择一个关于 A 的规则，的规则，并且把并且把 A 替

29、换替换成这条规则右边的字符串。成这条规则右边的字符串。b)如果如果栈顶是终结符栈顶是终结符 a，则读输入中的下一个符号，并且把，则读输入中的下一个符号，并且把它与它与 a 进行进行比较比较。如果它们匹配，则重复，如果它们匹配，则重复，否则，这个非确定性分支被拒绝。否则，这个非确定性分支被拒绝。c)如果如果栈顶是符号栈顶是符号$，则进入，则进入接受接受状态，状态，如果此刻收入已全部读完，则接受这个输入串。如果此刻收入已全部读完，则接受这个输入串。35严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。由CFG 构造 PDA输入输入:11

30、00CFG:S SS|1S0|101100S$At the beginning11001S0$PDA uses the rule S 1S0100S0$Input char is matchedNext charNext charNext char36严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。由CFG 构造 PDA输入输入:1100CFG:S SS|1S0|10100100$PDA uses the rule S 100000$Input char is matched00$Input char is matchedNext

31、 charNext charNext char37严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。由CFG 构造 PDA输入输入:1100CFG:S SS|1S0|10$Whole input string is processedThe$in the top of stack tells PDA the stack is empty.PDA accepts the stringNext charNext char38严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。由

32、CFG 构造 PDA的证明q采用一种缩写记号表示转移函数，即采用一种缩写记号表示转移函数，即一步把一个字符串写入一步把一个字符串写入到栈中到栈中。q设设 q 和和 r 是是 P 的状态，的状态，a，s。q要求要求 P，当读，当读 a 并且并且弹出弹出 s 时，从时，从 q 到到 r，并且同时把整个字，并且同时把整个字符串符串 u=u1u2ul 推入栈推入栈。可以如下完成这个动作：引入新的。可以如下完成这个动作：引入新的状态状态 q1,ql-1,并且令转移函数并且令转移函数(q,a,s)包含包含(q1,ul)(q1,)=(q2,ul-1)(ql-1,)=(r,u1)q使用记号使用记号(r,u)(

33、q,a,s)表示当表示当 q 是是 P 的状态，的状态，a 是下一是下一个输入符号以及个输入符号以及 s 是栈顶符号时，是栈顶符号时，PDA P 能够读能够读 a 和弹出和弹出s，然后把字符串，然后把字符串 u 推入栈和转移到状态推入栈和转移到状态 r。39严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。由CFG 构造 PDA的示意图qra,s xyzA shorthand notationqrq1q2a,s z,y,xUsing two dummy states to replace s by xyz at the top of

34、 the stack40严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。由CFG 构造 PDA的证明qP 的状态集的状态集 Q=qstart,qloop,qaccept E，E 实现上面描述的实现上面描述的缩写所需要的状态集合。缩写所需要的状态集合。q转移函数定义如下：从初始化栈开始，把符号转移函数定义如下：从初始化栈开始，把符号$和和 S 推入栈，推入栈，实现步骤实现步骤1的非形式描述：的非形式描述：(qstart,)=(qloop,S$),然后进行步骤然后进行步骤 2 循环循环处理情况处理情况1,此时栈顶为一变元。令此时栈顶为

35、一变元。令(qloop,A)=(qloop,w)|Aw 是是 R 中的一条规则中的一条规则处理情况处理情况2，这时栈顶是一个终结符。令，这时栈顶是一个终结符。令(qloop,a,a)=(qloop,)处理情况处理情况3，这时栈顶是空栈标记符。令，这时栈顶是空栈标记符。令(qloop,$)=(qaccept,)41严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。由CFG 构造 PDA的示意图qstartqloopstart,S$,A xyz for rule A xyza,a for terminal a,$qacceptshort

36、hand notation used here42严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例题例例2.14 把下述把下述CFG G转换成一台转换成一台PDAP1S aTb|bT Ta|见书见书74页。页。43严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。PDA与上下文无关文法的等价性引理引理引理引理2.152.15如果一个语言被一台下推自动机识别，则它是上下如果一个语言被一台下推自动机识别，则它是上下文无关的。文无关的。q为简化工作，对为简化工作，对P轻微修

37、改轻微修改:(1)有唯一的接受状态有唯一的接受状态,qaccept(2)在接受之前清空栈在接受之前清空栈(3)每一个转移把一个符号推入栈，或者把一个符号弹出栈，但不同时每一个转移把一个符号推入栈，或者把一个符号弹出栈，但不同时做这两个动作做这两个动作q使使P具有第三个特点，需要：具有第三个特点，需要：(1)把把同时同时push和和pop的转移替换成两个转移，中间要经过一个新的状的转移替换成两个转移，中间要经过一个新的状态；态；(2)把每一个既不把每一个既不push也不也不pop的转移，替换成两个转移，先推入任意一的转移，替换成两个转移，先推入任意一个栈符号，再把它弹出个栈符号，再把它弹出证明略

38、证明略44严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。PDA与上下文无关文法的等价性q对对P中的每一对状态中的每一对状态p,q,建立一个建立一个 CFG变量变量Apq q目标是使目标是使Apq 能准确地产生把能准确地产生把P从从 p和空栈和空栈 一块带到一块带到 q和空栈和空栈的所有字符串。的所有字符串。qPDA有两种方法可以从有两种方法可以从 p和空栈和空栈到到 q和空栈和空栈:(1)在到达在到达q之前栈变空之前栈变空这意味着我们从这意味着我们从p到某一个到某一个r(with empty stack)然后到达然后到达q(2)

39、在到达在到达q之前栈从不变空之前栈从不变空表明在表明在p时，我们时，我们push一些字符一些字符t进栈，在进栈，在q时，我们弹出时，我们弹出相同的字符相同的字符t45严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。PDA与上下文无关文法的等价性q对每一个对每一个p,q,r,增加规则增加规则q Apq AprArqq对每一个对每一个 p,q,r,s，当，当(r,t)(p,a,)且且(q,)(s,b,t),增加规则增加规则q Apq aArsb即,如果我们可以从p到r，并且从r到q，那么我们可以从p到q（这里，所有开始与结束时栈都为空

40、的即,如果我们可以从状态p到r，通过读一个字符a并且将t压入栈中，我们可以从状态s到达q，通过读字符b并且从栈中弹出t，那么如果我们开始状态p，栈为空，可以到达q，栈为空，通过读a，从r到s，然后读b获得46严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。PDA与上下文无关文法的等价性q对每一个对每一个 p,增加规则增加规则q App 即,我们可以从p到p，不需要读任何字符如果 Apq 果真可以准确地产生那些串，由P从p到q（栈为空），那么Aqstart,qaccept代表什么?where qstart denotes the s

41、tart state of PDA47严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。PDA与上下文无关文法的等价性q所以所以,在我们的文法中，将有所以的规则在我们的文法中，将有所以的规则 Apq 与与 Aqstart,qaccept 集合作为开始变元集合作为开始变元q剩下的就是证明剩下的就是证明 Apq 能通过能通过P中准确地产生那些串，从中准确地产生那些串，从p到到q（with empty stacks)q也就是说也就是说,我们需要证明我们需要证明如果如果 Apq 产生产生x,x 由由P 从从p 到到q(with empty

42、stacks)产生产生如果如果 x 由由 P 从从p到到q(with empty stacks),Apq 产生产生 xExercise:Prove the above two statements(Hint:by induction)48严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。主要内容主要内容2.1 上下文无关文法概述上下文无关文法概述2.1.1 上下文无关文法的形式化定义上下文无关文法的形式化定义2.1.2 上下文无关文法举例上下文无关文法举例2.1.3 设计上下文无关文法设计上下文无关文法2.1.4 歧义性歧义性2.1

43、.5 乔姆斯基范式乔姆斯基范式2.2 下推自动机下推自动机2.2.1 下推自动机的形式化定义下推自动机的形式化定义2.2.2 下推自动机举例下推自动机举例2.2.1 与上下文无关文法的等价性与上下文无关文法的等价性2.3 非上下文无关语言非上下文无关语言49严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。非上下文无关语言定理定理定理定理2.192.19关于上下文无关语言的泵引理关于上下文无关语言的泵引理如果如果 A 是上下文无关语言，则存在是上下文无关语言，则存在 p(泵长度泵长度)，使，使得得 A 中任何一个中任何一个长度不小于

44、长度不小于 p 的字符串的字符串 s 都能被都能被划分成划分成 5 段段 s=uvxyz，且满足下述条件：，且满足下述条件：(1)对于每一个对于每一个 i 0,uvixyiz A；(2)|vy|0；(3)|vxy|p。50严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。泵引理的证明思路q设设 A 是是 CFL，G 是产生是产生 A 的的 CFG。要证明。要证明 A 中任何足够中任何足够长的字符串长的字符串 s 都能够被抽取，并且抽取后的字符串仍在都能够被抽取，并且抽取后的字符串仍在A中。中。q设设 s 是是 A 中一个很长的字符串

45、。由于中一个很长的字符串。由于 s 在在 A 中，它可以用中，它可以用G 派生出来，从而有一棵语法树。由于派生出来，从而有一棵语法树。由于 s 很长，很长，s 的语法树的语法树一定很高，即，这棵语法分析树一定有一条很长的从树根一定很高，即，这棵语法分析树一定有一条很长的从树根的起始变元到树叶上的终结符的路径。根据鸽巢原理，在的起始变元到树叶上的终结符的路径。根据鸽巢原理，在这条长路径上一定有某个变元这条长路径上一定有某个变元 R 重复出现。重复出现。51严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。泵引理的证明思路SRRuzxv

46、ys=q把把 s 切成切成 5 段段 uvxyz，重复，重复第第 2 段和第段和第 4 段，得到的段，得到的字符串仍在字符串仍在A中。即，对任中。即，对任意意 i0，uvixyiz ASRuzRvyRvyx52严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。泵引理的证明思路泵长度q设设 G 是关于是关于 CFL A 的一个的一个 CFG，令，令 b 是规则右边符号数的最大值是规则右边符号数的最大值。q在在 G 的任意一棵语法树中，一个节点做多有的任意一棵语法树中，一个节点做多有 b 个儿子，即，离起始变元个儿子，即，离起始变元 1

47、 步最步最多有多有 b 片树叶；离起始变元不超过片树叶；离起始变元不超过 2 步最多有步最多有 b2 片树叶；离起始变元不超过片树叶；离起始变元不超过 h 步最多有步最多有 bh 片树叶。片树叶。q因此，如果语法树高度不超过因此，如果语法树高度不超过 h，则它产生的字符串的长度不超过，则它产生的字符串的长度不超过 bh。反之，。反之，如果一个产生的字符串长度不小于如果一个产生的字符串长度不小于bh+1，则生成它的每个语法树高度至少为，则生成它的每个语法树高度至少为 h+1.q设设 G 中变元的数目为中变元的数目为|V|。令泵长。令泵长 p=b|v|+1b|v|+1,则则 A 中任一长度不小于中

48、任一长度不小于 p 的的字符串字符串s的语法树的高度不小于的语法树的高度不小于|V|+1.q设设T是是s的一颗语法树，如果的一颗语法树，如果s有若干语法树，取有若干语法树，取T是结点数最少的，由是结点数最少的，由于于T的高度不小于的高度不小于|V|+1，从而，从而至少存在一条路径且其长度不小于至少存在一条路径且其长度不小于|V|+1并包含并包含|V|+2个节点，其中一个节点为终止符，其它为变元个节点，其中一个节点为终止符，其它为变元。q因此该路径上至少有因此该路径上至少有|V|+1个变元，而个变元，而G只有只有|V|个变元，故某个变元个变元，故某个变元R在在这条路径上不只出现这条路径上不只出现

49、1次，选取次，选取R为这条路径上在最下面的为这条路径上在最下面的|V|+1个变元个变元中重复出现的变元。中重复出现的变元。53严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。泵引理的应用例例2.20 用泵引理证明语言用泵引理证明语言 B=anbncn|n0 不是不是CFL。假设假设 B 是是CFL，令令 p 是由泵引理给出的泵长度是由泵引理给出的泵长度。选择选择 s=apbpcp，按照泵引理所述，可令按照泵引理所述，可令 s=uvxyz。由于由于 v 或者或者 y 不是空串，考虑下述两种情况：不是空串，考虑下述两种情况：(1)当当

50、 v 和和 y 都都只只含含有有一一种种符符号号时时，a 和和 b 或或 b 和和 c 不不会会都都在在 v中中，同同样样也也不不会会都都在在 y 中中，这这时时字字符符串串uv2xy2z 不不可可能能含含有有个个数数相相同同的的 a、b 和和 c。因因此此，它它不不属属于于 B，这这违违反反泵泵引引理的条件理的条件1，矛盾。，矛盾。(2)当当 v 和和 y 都都只只含含有有一一种种以以上上符符号号时时，uv2xy2z 可可能能含含有有个个数数相相同同的的 3 种种符符号号，但但是是这这些些符符号号的的顺顺序序不不可可能能正正确确。因此，它不属于因此，它不属于 B，矛盾。，矛盾。综上，综上，B