软件理论基础电子教案slide

DeterministicPDAandNormalDeterministicPDAandNormalFormsfor1DPDAandNormalFormsforCFGNormalFormsFor2DPDAandNormalFormsforCFGNormalFormsFor34定义一个P=(Q,,,,q0,Z0,F,(1)对于a或a=,X- X(2aa(qaX(qX5DeterministicPDA:Alloweda,b,b(deterministic6Alloweda,Alloweda,b ,ba,c,c(deterministic7Nota,bba,ba,b(nondeterministic8Not(q1,a,b)and(q1,ε,b)cannotoccurThis(q1,a,b)and(q1,ε,b)canbeexisted,buttheyaremutuallyexclusive.(nondeterministic9DPDAa,z0a,a b,ab,a q1,z0L(M){anbn:nAlanguageLiscalledaDeterministicPDA(DPDA)languageordeterministiccontext-languageifthereexistsaDPDAP=(Q,,,,q0,Z0,FthatacceptsL(M){anbn:nisaDPDAExampleofNon-DPDAL(M)a,xaxb,x(xz0,a,a,ab,bq ,z00q1NotallowedinNotallowedinb,x(xz0,a,a,ab,b ,z0HaveMorePowerthanItholdsSinceeveryDPDAisalsoaWewillactuallyWewillshowthatthereacontext- languageLwhichisnotacceptedbyanyDPDA不是任何DPDA的语言.DFAA=(Q,,A,q0,FP=(Q,,{Z0},P,q0,Z0,FP(q,a,Z0)={(p,Z0)}iffA(q,a)=LwcwrLwcwr={wcwRw0,1字符串}不是(Pum引理证明)，但它是如下DPDA的语言：0,x/0x1,x/(x=Z0,0,0,0/0,1/q0c,Z0/c,0/c,1/q1ε,Z0/q2L是某终态接受的DPDAPL=L(P).(证明:留作练习).以L是某个空栈接受的DPDA的语言；受的DPDAP,使得N(P)={0}*.方法构造与DPDACFG可证对于任何L’={w$w$.L=Lwwr={wwRw0,1字符串非固有二义的.即存在非二义文法S0S01S1存在非固有二义的CFGL不是任何DPDAP的语言.DPDA语言的集合要比CFG的非固有二义AaaAAabBc|BBAaaArInABBAxBz|xy1rNormalFormsforNormalFormsfor EliminatingUselessEliminatingUnitSimplificationsofCFGandNormalFormsForrSaBrSaBABbBSabAAB SaBABbrBSaB|abAaaABGeneratingGeneratingSymbolandReachableGeneratingReachable步骤CFGGVTSP可通过下基础aT归纳A,(VT)*的证明思路:一方面，所得符号的确是产生符号；––CFGG=(V,T,S,PwwT*，(VT– EliminatingUselessEliminatingUnitSimplificationsofCFGandUselessSaSbSUselessSaSbSS UselessASomederivationsneverSAaAaaAaaaA SAAAB UselessNotreachablefromRemovingRemovingUselessExampleCFGG=({S,A,B,C},{a,b},S,PSaS|A|ABCFirst:findallvariablesthatcanproducestringswithonlyterminalsSaS|A|ABCRound1:{a,b,A,SRound2:{a,b,A,B,CFGCFGGVTSPL(G)号的产生式，得到CFGG2=(V2,T2,S,号的产生式，得到CFGG1=(V1,T1,S,步骤CFGGVTSP可通过下列AA证明思路:一方面，所得符号的确是可达符号；另一方面，对任何w,KeeponlytheKeeponlythethatproduceterminal (therestvariablesareSaS|A|ABCSaS|ABRemoveuselessSecond:FindallreachablefromUseaDependencySaS|ABS reachablefromS(therestvariablesareFinalrSaS|ABSaS|ARemoveuseless举例PDA构造CFGGV,{0,1}S其中V{SpYq]p,q{q0,q1,q2(1)SSS0,Z/0,X/1,X1,X[q0Z0qj]0[q0Xqi][qiZ0qj],i,j=0,1,2((q0,XZ0)(q0,0,[q0Xqj]0[q0Xqi][qiXqj],i,j=0,1,2((q0,XX)(q0,0,[q0Xq1]1((q1,)(q0,1,[q1Xq1]1((q1,)(q1,1,[q1Z0q2] S[q0Z0q0];S[q0Z0q1];S[q0Z0q2][q0Z0qj]0[q0Xqi][qiZ0qj],i,j=[q0Xqj]0[q0Xqi][qiXqj],i,j=0,1,2;[q0Xq1]1;[q1Xq1]1;[q1Z0q2]S[q0Z0q2][q0Xq1]0[q0Xq1][q1Xq1];[q0Xq1]1; [q1Xq1]1;[q1Z0q2];为简捷记[q0Z0q2为Aq0Xq1为[q1Xq1]为Cq1Z0q2为SA;A0BD;BB1;C DCFGGVTSP通过下列步骤可以消去G中产生式及其影响：(1)G Amk个可空符号，则该产生式能够对应G1中的2m个产生式；L(G1)=L(G)-NormalFormsNormalFormsfor EliminatingUselessEliminatingUnitSimplificationsofCFGand、SA;A0BD;BB1;C DSSA;A0BD;BB1;C D CFGGVTSPAV 步骤CFGGVTSP)，可通过下列归基础AA是一个可空符号；归纳BC1C2…CkExampleExampleFinalrSaMbMMMSaMb|MaMb|NullableSA;A0BD;BB1;C DSA;A0BD;A0B;B0BC;B1;C1.NormalFormsfor EliminatingUselessEliminatingUnitSimplificationsofCFGand可简化某些证明，减少推导步数,利于文 单一偶对(unitCFGGVTPSABV步骤CFGGVTSP可通过下列基础AVA是一个单一偶对；归纳(AChomskyNormalForm上下文无关文法CFGGV,T,S,P)Chomsky范式A→ A其中A,B,C是变量，aSSaSASSAASASAANormalSSA;A0BD;A0B;B0BC;B1;C1.(SSAABBCCDS0BD;S0B;A0BD;A0B;B0BC;B1;C1.生新的无用符号，如本例中变量A和DCFGGVTS,PG1=(V,T,S,P1(A,B),G1中加入产生式AB为一非单一产生式；G1G定理:上述步骤从G构造G1,有L(G1)=,NormalFormsfor EliminatingNormalFormsfor EliminatingUselessEliminatingUnitSimplificationsofCFGandCFGGV,T,S,P可以通过下列步骤对G进行简化：Step1:Remove-Step2:RemoveUnit-Step3:RemoveUseless CFGG的字符串，通过上述步骤从G构造G1，则有L(G1)=L(G)-P-251Ex.6.4.2(c其中m≠0任意P-251Ex.6.4.3P-271P-272P-251Ex.6.4.3P-272That’sallforThankaA并增加新的产生式Aa；,采用级连(cascade方法转变为只含两个非终结符；引入k-2个新的非终结符C1,C2,…,Ck-2,AB1C1,C1B2C2,…,Ck-3Bk-2Ck-Ck-2Bk-得