形式语言与自动机理论电子教案.pptVIP

6.2.2去ε-产生式**证明对于任意w∈T+，A?nGw的充分必要条件是A。必要性：设A?nGw，施归纳于n，证明A?mG′w成立。当n=1时，由A?Gw知，A?w∈P，按照定理所给的构造G′的方法，必定有A?w∈P′。所以，A?G′w成立。6.2.2去ε-产生式**?*Gw1w2…wm?*Gw1w2…XmA?X1X2…Xm其中w1w2…wm=w，且w1，w2，……，wm∈T*。…设n≤k时结论成立(k≥1)，当n=k+1时?*Gw1X2…Xm6.2.2去ε-产生式**注意到w≠ε，必存在1≤i≤m，wi≠ε，设i，j，…，k是w1，w2，…，wm中所有非空串的下标，并且1≤i≤j≤…≤k≤m，即：w=wiwj…wk按照G′的构造方法，A?XiXj…Xk∈P′12345Xi?*G′wi，Xj?*G′wj，…，Xk?*G′wk。再由归纳假设，6.2.2去ε-产生式**A?*G′XiXj…Xk?*G′wiwj…Xk?*G′wiwj…wk?*G′wiXj…Xk…所以，结论对n=k+1成立。由归纳法原理，结论对所有的n成立。6.2.2去ε-产生式**充分性：设A?mG′w，施归纳于m，证明A?nGw成立。01当m=1时，由A?G′w知，A?w∈P′，按照定理所给的构造G′的方法，必定有A?α∈P。A?w是通过删除产生式A?α右部中的可空变量而构造出来的，所以，02A?Gα?*Gw成立。036.2.2去ε-产生式**设n≤k时结论成立(k≥1)，当m=k+1时1A?*G′XiXj…Xk2?*G′wiXj…Xk3?*G′wiwj…Xk4…5?*G′wiwj…wk=w6其中Xi?*G′wi，Xj?*G′wj，…，Xk?*G′wk。76.2.2去ε-产生式**从而，表明A?XiXj…Xk∈P′。按照G′的构造方法，必定存在A?X1X2…Xm∈P′，而且{X1，X2，…，Xm}-{Xi，Xj，…，Xk}?U{Xi，Xj，…，Xk}?{X1，X2，…，Xm}?*GXiXj…XkA?GX1X2…Xm6.2.2去ε-产生式**再根据Xi?*G′wi，Xj?*G′wj，…，Xk?*G′wk和归纳假设，有Xi?*Gwi，Xj?*Gwj，…，Xk?*Gwk。这表明，如下派生成立：A?GX1X2…Xm ?*GXiXj…Xk ?*GwiXj…Xk ?*Gwiwj…Xk … ?*Gwiwj…wk=w6.2.2去ε-产生式**表明结论对m=k+1成立。由归纳法原理，结论对任意m成立。01020304注意到A的任意性，当S=A时结论成立。即：S?*Gw的充分必要条件是S?*G′w亦即：L(G′)=L(G)-{ε}。05定理得证。6.2.3去单一产生式**T?T*F|T/F|FF?F↑P|PP?(E)|N(L)|idN?sin|cos|exp|abs|log|intL?L,E|E文法Gexp1：E?E+T|E-T|TE?T?F?P?id存在派生：6.2.3去单一产生式**P?(E)|N(L)|id4N?sin|cos|exp|abs|log|int5Gexp3：E?E+T|E-T|T*F|T/F|F↑P|(E)|N(L)|id1T?T*F|T/F|F↑P|(E)|N(L)|id2F?F↑P|(E)|N(L)|id3L?L,E|E该文法中不存在类似的派生。66.2.3去单一产生式**01020304单一产生式(unitproduction)定理6-8对于任意CFGG，ε?L(G)，存在等价的CFGG1，G1不含无用符号、ε-产生式和单一产生式。形如A?B的产生式称为单一产生式。满足本定理的CFG为化简过的文法。05已有去无用符号和去ε-产生式的结论，所以只讨论去单一产生式的问题。证明要点：6.2.3去单一产生式**构造G2，满足L(G2)=L(G)，并且G2中不含单一产生式。用非单一产生式A1?α取代A1?*GAn?α用到的产生式系列A1?A2，A2?A3，…，An-1?An，An?α。其中，A1?A2，A2?A3，…，An-1?An都是单一产生式。（n≥1）126.1.2二义性**句子x+x/y↑2在文法中的三个不同的最左派生E?E+E?x+E?