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

第六章 上下文无关语言的性质 CFL的泵作用引理 CFL有与正规集类似的泵作用引理。 引理6.1：设L为任何CFL，则存在一个只依赖于L的常数n，使得若z?L，且|z| ≥ n，则可以把z写成z = uvwxy，使得 (1) |vx| ? 1， (2) |vwx| ? n (3) 对任何 i ? 0，uviwxiy在L中。 CFL的泵作用引理 证明：设G为产生L-{ε}的Chomsky范式的文法。 {ai bj ci dj | i, j ?1}?CFL 例6.2：设L2 = {ai bj ci dj | i, j ?1}。 假设L2?CFL，令n为引理中常数。取z = anbncndn。设z = uvwxy满足泵作用引理条件。 由于|vwx|≤n，vx最多含有两种不同的符号。 若vx?a+，则uwy含的a少于c， uwy ?L2，矛盾。 若vx?b+， vx?c+ 或vx?d+，我们作类似的处理。 若vx含有a和b，则uwy显然含有少于c的a。如果vx含有b和c或c和d，也会发生同样的矛盾。 无论如何都与引理矛盾，故L2?CFL。 CFL不含交叉结构 从这个例子中我们可以看到CFL不含交叉结构的。CFG可以描述并列结构和嵌套结构，但是不能描述交叉结构。 Ogden引理 引理6.2：设L为CFL，则存在一个常数n（事实上它可以和泵作用引理中一样），使得如果z是L中的任意一个字，并且在z中任意标记了n个或多于n个的符号，则可写成z = uvwxy，使得 (1) v和x一起至少含有一个被标记的符号 (2) vwx最多有n个被标记的符号，和 (3) 对所有的i ≥ 0，uvi wxi y在L中。 Ogden引理的应用 例6.3：设L4 = {ai bj ck | i ? j，j ? k且i ? k}。 假设L4?CFL且常数为n，取z = anbn+n!cn+2n!。标记所有a。令z = uvwxy。显然vx?a+b*或vx?a+c* ，若x?b*或x?c*，则v?a+。若x?a+，则v?a*。 考虑x?b*，则v?a+。设p=|v|，1?p?n，p整除n!，令整数q满足pq = n!，则z’ = uv2q+1wx2q+1y ?L4。又v2q+1 = a2qp+p = a2n！+p。因uwy只含(n – p)个a，故z’含有(2n!+n)个a。但是由于v和x中不含c，所以z’ 仅含(2n！+ n)个c，从而z’?L4。矛盾。 若x?a+或x? c*中，也同样矛盾。故L4?CFL。 上下文无关语言的封闭性质 对并，联结和Kleene闭包等运算是封闭的。 对替换是封闭的。 对同态是封闭的。 对逆同态是封闭的。 CFL对逆同态是封闭的 定理6.3：上下文无关语言对逆同态是封闭的。 证明：设同态h：?→△*，L?CFL，设L =L(M)，其中M是PDA。 CFL对交和补不封闭性 定理6.4：上下文无关语言对交运算不封闭。 证明：语言L1= {aibici | i?1}?CFL。显然，语言L2={aibicj | i , j ?1}和L3={aibjcj | i , j ?1}都是CFL。但是，L2∩L3= L1。如果CFL对交封闭，则L1应是CFL。矛盾。因此上下文无关语言对交运算不封闭。 推论：上下文无关语言对补运算不封闭。 CFL与RL的交是CFL 定理6.5：若L?CFL，R ?RL，则L∩R ? CFL。 L1 = {ww | w?(a+b)*} ? CFL 例6.5：设L1 = {ww | w?(a+b)*}。L ?CFL。 假设L1?CFL，则L’ = L1∩a+b+a+b+ ?CFL。但是L’ = {aibjaibj | i , j ?1}。用泵作用引理不难证明L’ ?CFL 。 所以L ?CFL 。 注意：这里如果直接应用泵作用引理去证明，则是不成功的。应用CFL与RL的交是CFL，则可以使其交得到一种形式上的规范，从而可以成功地应用泵作用引理。 L1的补是CFL? 例6.6：设L2={a, b}*–{ww | w?(a+b)*}。L2 ?CFL? 显然L2的字都具有前一半与后一半不相同的特性。 L1的补是CFL? 符号串的前一半与后一半如下图所示：其中x与y位置相同，且x ? y。 L1的补是CFL 符号串的前一半与后一半如下图所示：其中x与y位置相同，且x ? y。 CFL的某些判定算法 定理6.6：存在算法来判断一个CFL是否为(a)空集，(b)有穷集，或(c)无穷集。 证明：可以用泵作用引理来检测。但是这样产生的算法的效率是很差的。 检测CFL是否为空可用测试判定一个变量是否产生任何终极符号串的算法。显然，L(G)非空，当且仅当开始符号S产生某终极符号串。 为了检测L(G)是有穷的，可以用