计算理论导引-2-上下文无关文法

1计算理论2主要内容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.1与上下文无关文法的等价性2.3非上下文无关语言3上下文无关文法(CFG)概述A0A1ABB#替换规则变量(Variables)A,B终止符(Terminals)0,1,#起始变元(StartVariable)A箭头的左侧只有一个变量替换规则又称为产生式4如何利用CFG产生字符串A0A1ABA#获取一个字符串的替换过程叫派生。例如字符串000#111的过程如下：A0A100A11000A111000B111000#111(1)写下起始变元——第一条规则左边的变元。(2)取一个已写下的变元，并找到以该变元开始的规则，把这个变元替换成规则右边的字符串。(3)重复步骤2，直到写下的字符串没有变元。5如何利用CFG产生字符串A0A1ABA#可以用语法生成树形象地表示派生过程。AAAB#000111A6文法的语言A0A1ABA#文法G1可以产生的字符串包括：#,0#1,00#11,000#111,…用文法生成的所有字符串的集合称为文法的语言。L(G1)表示文法G1产生的语言。L(G1)={0n#1n|n0}用上下文无关文法产生的语言叫上下文无关语言。文法G1的简写：A0A1|BB#7上下文无关文法的形式化定义定义2.1上下文无关文法是一个4元组(V,,R,S)，且(1)V是一个有穷集合，称为变元集。(2)是一个与V不相交的有穷集合，称为终结符集。(3)R是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成。(4)SV是起始变元。8CFG的术语假设u与v由变元及终结符构成的字符串，Aw是文法的一条规则，称uAv生成uwv，记作uAvuwv。如果u=v，或者存在u1,u2,…,uk,k0使得uu1u2…ukv，则称u派生v，记作u*v。文法G=(V,T,R,S)的语言为L(G)={wT*|Sw}9上下文无关文法举例例2.1考虑文法G=({S},{a,b},R,S)，其中规则集R为：SaSb|SS|。该文法生成abab，aaabbb，aababb，…如果将a看作(，将b看作)，L(G)是所有正常嵌套的括号字符串构成的语言。10设计上下文无关文法设计如下语言的上下文无关文法{0n1n|n0}∪{1n0n|n0}{0n1n|n0}{1n0n|n0}设计技巧化繁为简，利用正则，考察子串，利用递归。11设计上下文无关文法CFGforL1={0n1n|n0}S0S1|CFGforL2={1n0n|n0}S1S0|CFGforL1∪L2SS1|S2S10S11|S21S20|CFGforL3={02n13n|n0}?S00S111|12上下文无关文法与正则语言任何正则语言可以由CFG描述。如果(qi,a)=qj，则增加规则ViaVj如果qi是接受状态，则增加规则Vi如果q0是起始状态，则V0是起始变元。q0q110start01DFACFGG=({V0,V1},{0,1},R,V0)V00V0|1V1|V11V1|0V013最左派生对于文法G中的一个字符串w的派生，如果在每一步都是替换左边剩下的变元，则称这个派生是最左派生。例如G=({S},{(,)},R,S)，其中规则为S(S)|SS|SSS(S)S()S()(S)()()SSSS(S)(S)(S)()(S)()()14歧义性一个串可能有两个甚至更多的最左派生。例如CFGG=({S},{+,*,a},R,S)，其中规则为SS+S|S*S|a产生串a+a*aSS+Sa+Sa+S*Sa+a*Sa+a*aSS*SS+S*Sa+S*Sa+a*Sa+a*aSSSSS+aaaxSSSSSx+aaa15歧义性定义2.4如果字符串w在上下文无关文法G中有两个或两个以上不同的最左派生，则称G歧义地(ambiguously)产生字符串w，如果文法G歧义地产生某个字符串，则称G是歧义的。某些上下文无关语言只能用歧义文法产生，这样的语言是固有二义的。16乔姆斯基范式定义2.5称一个上下文无关文法是为乔姆斯基范式(Chomskynormalform)，如果它的每一个规则具有如下形式：ABCAa其中a是任意的终结符，A、B和C是任意的变元，且B和C不能同时是起始变元。此外，允许规则S，其中S是起始变元。17乔姆斯基范式定理2.6任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。Step1:增加起始变元S0和规则S0S,其中S是原来的起始变元。Step2:考虑所有的规则。对于A,删去每个A都会产生一个新规则。例如RuAvAwRuAvw,RuvAw,Ruvw18乔姆斯基范式定理2.6任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。Step3:考虑单一产生式AB。例如：AB,BaC,BCC,则增加AaC,ACC。Step4:考虑Au1u2…uk,其中k2且ui是变量或终结符。替换该规则Au1A1,A1u2A2,A2u3A3,…,Ak-2uk-1uk19例题SASA|aBAB|SBb|S0SSASA|aBAB|SBb|20例题Afterthat,weremoveBS0SSASA|aBAB|SBb|S0SSASA|aB|aAB|S|BbBeforeremovingBAfterremovingB21例题Afterthat,weremoveAS0SSASA|aB|aAB|S|BbBeforeremovingAAfterremovingAS0SSASA|aB|a|SA|AS|SAB|SBb22例题Then,weremoveSSandS0SAfterremovingSSAfterremovingS0SS0SSASA|aB|a|SA|ASAB|SBbS0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAB|SBb23例题Then,weremoveABBeforeremovingABAfterremovingABS0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAB|SBbS0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAb|SBb24例题Then,weremoveASBeforeremovingASAfterremovingASS0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAb|SBbS0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAb|ASA|aB|a|SA|ASBb25例题Then,weapplyStep4BeforeStep4AfterStep4GrammarisinCNFS0ASA|aB|a|SA|ASSASA|aB|a|SA|ASAb|ASA|aB|a|SA|ASBbS0AA1|UB|a|SA|ASSAA1|UB|a|SA|ASAb|AA1|UB|a|SA|ASBbA1SAUa26主要内容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.1与上下文无关文法的等价性2.3非上下文无关语言27下推自动机考虑语言{0n1n|n≥0}的识别装置xyz$状态控制器栈下推自动机(pushdownautomata)PDA=NFA+stackwithunlimitedsize确定型PDA和非确定型PDA的语言识别能力不相同。aabb28下推自动机(PDA)的形式化定义定义2.8下推自动机是6元组(Q,,,,q0,F)(1)Q是一个有穷集合，称为状态集。(2)是一个有穷集合，称为输入字母表。(3)是一个有穷集合，称为栈字母表。(4):Q××P(Q×)是转移函数，其中=∪{},=∪{}(5)q0∈Q是起始状态。(6)FQ是接受状态集。PDA的形式化定义没有提供检验空栈的直接手段。约定PDA在开始时就把一个特殊符号$放入栈中。29PDA的计算过程PDAM=(Q,,,,q0,F)接受输入串w，如果能够把w写成w1w2…wm，其中wi∈存在状态序列r0,r1,…,rm∈Q存在s0,s1,…,sm∈*满足下述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F30下推自动机举例例2.9描述识别语言{0n1n|n0}的PDAM。q1q2q3q4,$1,00,01,0,$M=({q1,q2,q3,q4},{0,1},{0,$},,q1,{q1,q4}),(q1,,)={(q2,$)},(q2,0,)={(q2,0)}(q2,1,0)={(q3,)},(q3,1,0)={(q3,)}(q3,,$)={(q4,)},(q,x,y)={}31下推自动机举例例2.10构造识别语言{aibjck|i,j,k0且i=j或i=k}的PDAM。q1q2q5q6,$a,a,$q7q3q4,,,$b,c,a,c,b,a32下推自动机举例例2.11构造识别语言{wwR|w∈{0,1}*}的PDAM。q1q2q3q4,$0,01,10,01,1,,$33PDA与上下文无关文法的等价性定理2.12一个语言是上下文无关的，当且仅当存在一台下推自动机识别它。引理2.13如果一个语言是上下文无关的，则存在一台下推自动机识别它。引理2.15如果一个语言被一台下推自动机识别，则它是上下文无关的。34PDA与上下文无关文法的等价性引理2.13如果一个语言是上下文无关的，则存在一台下推自动机识别它。设A是一个CFL，根据定义，存在一个CFGG产生它。如何把G转换成一台等价的PDAP。通过确定是否存在关于输入w的派生，当G产生w时，PDAP接受这个输入。设计P，以确定是否有一系列使用G的规则替换。35由CFG构造PDAP的非形式化描述如下：(1)把标记符$和起始变元放入栈中。(2)重复下述步骤：a)如果栈顶是变元A，则非确定地选择一个关于A的规则，并且把A替换成这条规则右边的字符串。b)如果栈顶是终结符a，则读输入中的下一个符号，并且把它与a进行比较。如果它们匹配，则重复，否则，这个非确定性分支被拒绝。c)如果栈顶是符号$，则进入接受状态，如果此刻收入已全部读完，则接受这个输入串。36由CFG构造PDA输入:1100CFG:SSS|1S0|101100S$Atthebeginning11001S0$PDAusestheruleS1S0100S0$InputcharismatchedNextcharNextcharNextchar37由CFG构造PDA输入:1100CFG:SSS|1S0|10100100$PDAusestheruleS100000$Inputcharismatched00$InputcharismatchedNextcharNextcharNextchar38由CFG构造PDA输入:1100CFG:S