形式语言学ch8.pdfVIP

第8章上下文无关语言的性质 本章讨论CFL 的性质 主要内容 CFL 的泵引理及其应用、Ogden引理。 CFL 的封闭性 • 封闭运算：并、乘、闭包、代换、同态映射、逆 同态映射 • 不封闭运算：交、补 第8章上下文无关语言的性质 CFL 的判定算法。 判定CFG产生的语言是否为空、有穷、无穷。 一个给定的符号串是否为该文法产生的语言的一个句 子等问题。 重点 CFL 的封闭性、CFL的泵引理。 难点 CFL 的泵引理的应用、CFL 的同态原象是CFL 。 1 8.1 上下文无关语言的泵引理 启发 RG G=(V ，T，P ，S)，使得L(G)=L ，当x足够长时，如 |x|≥|V|+1时，存在u 、v 、w ∈T* ，|v|≥1，使得x=uvw ， 当G为右线性文法时，必定存在语法变量A ，使得如下派 生成立： * * * * i * i S⇒ uA⇒ uvA⇒ ……⇒ uv A⇒ uv w V是可以被重复任意多次的字串！ CFL也有类似性质？ 8.1 上下文无关语言的泵引理 CFL 的自嵌套特性：如果L是一个CFL，CFG G=(V，T， P ，S)是产生L 的文法。当L是一个无穷语言时，必存在 w ∈L ，A ∈V ，α，β∈(V ∪T)* ，且α和β中至少有一 个不为ε，使得如下派生成立 * + + S⇒ γA δ⇒ γαA βδ⇒ z 文法G 中存在有如下形式的派生 A⇒+ αA β 2 8.1 上下文无关语言的泵引理 这种类型的派生预示着 * + + S⇒ γA δ⇒ γαA βδ⇒ z 并且 * + n n + S⇒ γA δ⇒ γαA β δ⇒ z ′ * * * * S⇒ γA δ 设α⇒ v ，β⇒ x ，γ⇒ u ， * ⇒ u αA βδ A⇒* * w ，δ⇒ y ⇒* u αA βy 可以得到如下派生 … * n n ⇒ u α A β y * n n ⇒ uv Ax y * n n ⇒ uv wx y 乔姆斯基范式文法 乔姆斯基范式文法(Chomsky normal form ，CNF)简称为 Chomsky文法，或Chomsky范式。 CFG G=(V，T，P ，S)中的产生式形式： A→BC ，A→a 其中，A 、B 、C ∈V ，a ∈T 。 CNF中，不允许有ε-产生式、单一产生式。 3 乔姆斯基范式 例6-3-1 试将文法G 转换成等价的 G