中文XML论坛--北京大学计算机系“理论计算机科学基础”2006年期末试题 zz

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

（每题10分，共60分）

1.语言L={x|x=xR, x属于{0,1}* } 其中xR是x的倒转
(1)证明：L不是正则语言
(2)证明：L是上下文无关语言

2.A={<M,x>|TM M接受x}
(1)证明A是可识别的
(2)证明A不是可判定的

3.任意举出两个PSPACE完全的语言A，B
  A={   |      }
  B={   |      }
  构造A到B的映射规约证明并分析代价

4.两个问题：
对于一个有向图，求出两点间最长路径
对于一个有向图，求出两点间最短路径

  (1)将两个问题转化为数学语言
  A={   |      }
  B={   |      }

  (2)对于A
     I.属于哪个复杂性类
     II.证明之
     III.证明是这个复杂性类完全的

  (3)对于B
     I.属于哪个复杂性类
     II.证明之
     III.证明是这个复杂性类完全的

5.判断以下十句话是正确的(打对号),错误的(打X),还是未知正确性(打?)

P=NP
P=EXPTIME
coNP=NP
coNL=NL
NL=PSPACE
PSPACE=NPSPACE
P=PSPACE
TIME(2^n)=TIME(3^n)
其他2个忘了，和这些都差不多

6.将以下各种类的关系用哈斯图表示出来
L,NL,coNL,P,NP,coNP,PSPACE,NPSPACE,EXPTIME,SPACE((logn)^2)

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我一道都不会做

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

貌似是很基本的东西。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

看不懂题目,说的是什么,谁能给个参考答案

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

第一题，即证明{0,1}*中的回文字符串(1)不是正则语言，(2)而是上下文无关语言

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

第一题的解答,以下说明中的 x(n)表示n个x的连接.
(1) 证明: 假设语言L是正则语言, 现在考虑语言L1={1(n)0(n)1(n), n≥1}.显然L1是L的子集.如果能证得L1不是正则语言,则L也不是正则语言.
             根据泵引理, 存在N≥1, 取字符串z=1(N)0(N)1(N), z可分解为三部分u,v,w,
             即z=uvw,且满足|uv|≤N, |v|≥1.
             因为 v非空, 又因为|uv|≤N, 所以v只能是由1组成的字符串, 可以设v=1(k), k≥1.
             此时有: u=1(N-k-i)
                        w=1(i)0(N)1(N)
             从而有:uv(i)w=1(N-k-i) (1(k))(i) 1(i)0(N)1(N)=1(N+(i-1)k)0(N)1(N)
             根据泵引理, 如果L1是正则语言, 那么对于任意的i, uv(i)w都属于L1.
             但是, 存在i=2时, N+(i-1)k=N+k>N, 其中k≥1, 这时,1(N+k)0(N)1(N)不属于L1, 这与泵引理矛盾.
             所以, L1不是正则语言, L也不是正则语言. 证毕.

(2) 证明: 归纳法证明L是上下文无关语言.
     首先构造文法产生式集合A如下:
              P->ε; P->0; P->1; P->0P0; P->1P1.
     因此可以得到一个CFG G=({P}, {0, 1}, A, P).

     原命题等价于: x∈L, 当且仅当x∈L(G).

     证明第一部分(当), 即证如果x∈L(G) , 则 x∈L.
           因为x∈L(G), 所以总是有P=*>x.则有以下证明:
           基础: P=*>x的推导为1步完成, 即P=>ε或者P=>0或者P=>1, 由于 ε, 0, 1都属于L, 所以x∈L.
           归纳: 假设对于任何n步完成的推导P=*>y都有y∈L, n≥1.
                  考虑x的(n+1)步推导, 形式必然为:
                        P=>0P0=*>0y0=x 或者 P=>1P1=*>1y1=x.
                   根据归纳假设, y∈L, 所以x∈L.

     证明第二部分(仅当), 即证如果x∈L, 则 x∈L(G)
           归纳基础: |x|=0或者|x|=1, 则x一定等于ε, 0, 或者1, 由于根据产生式P->ε, P->0, P->1推导出的x属于L, 所以在上述任一情况下, 都有P＝*>x.
           归纳: 假设|x|≥2, 因为x=xR, 所以x的开头和结束一定是同一个符号, 即x=0y0或x=1y1, 其中y=yR, 即y也属于L.
             如果x=0y0, 根据归纳假设有P=*>y, 故可以得到一个从P到x的一个推导:
                 P=>0P0=*>0y0=x.
             如果x=1y1, 方法类似.
     所以,对于任意的x∈L, 总存在一个推导, 能通过产生式A生成该x, 所以x∈L(G).

    综上所述, L是上下文无关语言. 证毕.

[此贴子已经被作者于2007-1-26 22:38:55编辑过]


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	1,297.852ms