计算机数学基础第四章.pptVIP

计算机科学的数学基础 第四章 上下文无关语言 CFG与CFL 设文法G = (V, T, P, S)，若，对于?? ? ? ? P，满足? ? V，? ? (V ? T)*，则称G为2型文法或CFG。 CFG的产生式为A ? ?形式，即其右部只有单一的非终极符A，表明用?来取代A时，与A所在的上下文无关。故称为上下文无关文法。 CFG定义的语言称为CFL，记为L(G), L(G) = {w | w?T*且S ?*w}。 上下文无关文法的简化 无效符号：1、不出现在任何句型中的符号；2、不能产生终极符号串的符号， ?生成式：右部为?的生成式。 单元生成式：形为A?B的生成式，A, B?V。 定理4.4：每个不含?的上下文无关语言都可用一个没有无效符号，?生成式和单元生成式的上下文无关文法来定义。 Chomsky范式 定理4.5（Chomsky范式，或CNF）：任意不含?的上下文无关语言都能由这种文法产生，其中所有生成式的形式都是A → BC或A → a。在这里A，B和C都是变量，而a是终极符。 Chomsky范式文法的任何一棵语法树都是一棵二叉树。 Greibach范式 定理4.6(Greibach范式，或GNF)：每一个不含?的上下文无关语言L都能由这样一种文法产生，其生成式的形式都是A → a?，这里A是一个变量，a是一个终极符，而?是变量的（可能为空）符号串。 Greibach范式文法的每个句子的推导步数等于句子的长度。 先天歧义的CFL的存在 考虑语言 L = L1∪L2， 其中： L1={anbncmdm∣n ? 1, m ? 1}， L2={anbmcmdn∣n ? 1, m ? 1}。 先天歧义的CFL的存在 若任何生成L的文法一定有两个完全不同的部分来分别生成L1与L2。 CFG的变量一定是递归的 引理4.6：设G为无歧义CFG，则可有效地构造等价的无歧义的CFG G?，使得G?是简化的且对?A，A ? S，有派生A ?*G? X1AX2且X1和X2不同为?。 证明：简化文法的操作都不会引入歧义性。 假设?非递归的变量A，则用所有A生成式的右部替换出现在任何一个生成式的右边的A，然后删去A，则剩下变量均有派生A ?* X1AX2且X1和X2不同为?，除非该文法所定义的语言是有穷的。 显然这一操作同样不会引入歧义性。 因此无歧义的G有满足条件的等价的无歧义的G’。 L的无歧义文法有两个部分 证明：假设L无歧义，则可以构造L的一个满足引理4.6的G。 文法G满足下列性质：则 ⒈若A ?* X1AX2， X1和X2都仅含一种符号； ⒉若A ?* X1AX2， X1和X2所含符号不同。 ⒊若A ?* X1AX2， |X1|= |X2|。 ⒋若若A ?* X1AX2，且有A ?* X3AX4，则X1和X3、X2和X4所含符号相同。 L的无歧义文法有两个部分 ⒌X1和X2必是下列四种情形之一： ⑴ X1含a而X2含b； ⑵ X1含a而X2含d； ⑶ X1含b而X2含c； ⑷ X1含c而X2含d。 L的无歧义文法有两个部分 把G分成下列两个文法： G1= ({ S }∪Cab∪Ccd，T，P1，S)， G2= ({ S }∪Cad∪Cbc，T，P2，S)， 其中P1包括P中所有含Cab或Ccd的变量的生成式及所有形如S → anbncmdm的生成式， m ≠ n ；P2包括P中所有含Cad或Cbc的变量的生成式及所有形如S → anbncmdm的生成式， m ≠ n 。 P中形为S → anbncndn的生成式则不在P1或P2中。 啊哈！大功告成！因为：G1∩G2 = ?，且L1=L(G1)， L2=L(G2)。故L3中的句子既可由G1生成又可由G1生成，从而L是歧义的。 事情还没有这么简单 这里还有两个细节要证明： 只有有穷个(n, n)未被囊括 引理4.5：设(Ni, Mi)，1 ≤ i ≤ r，为整数集的对偶。（这些整数集可以是有穷的或者无穷的。）设 Si = {(n, m)∣n在Ni中，m在Mi中}， 并设S = S1∪S2∪…∪Sr。 若对所有的n和m，这里m ≠ n，每个整数对(n, m)在S中，则对除去某个有穷集外的所有n，(n, n)在S中。 只有有穷个(n, n)未被囊括 证明：假设? n?m, (n, m)?S且无穷多 (n, n)?S。 设Γ= {(n, n) | (n, n)?S}。构造Γ?Γr ? Γr–1?… ? Γ1, Γi无穷且?n, m ?Γi, (n, m) ? Si∪…∪Sr。 Γ中或n? Ni或n? Mi,否则(n, n)?Si从而(n, n)?S。 于是或有Γi+1的无穷子集不在Ni中，或有Γi+1的无穷子集不在Mi中.总之都可令此无穷子集为