以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 理论计算机科学 』 (http://bbs.xml.org.cn/list.asp?boardid=64) ---- 北京大学计算机系“理论计算机科学基础”2006年期末试题 zz (http://bbs.xml.org.cn/dispbbs.asp?boardid=64&rootid=&id=34640) |
-- 作者:Logician -- 发布时间:6/20/2006 2:56:00 PM -- 北京大学计算机系“理论计算机科学基础”2006年期末试题 zz (每题10分,共60分) 1.语言L={x|x=xR, x属于{0,1}* } 其中xR是x的倒转 2.A={<M,x>|TM M接受x} 3.任意举出两个PSPACE完全的语言A,B 4.两个问题: (1)将两个问题转化为数学语言 (2)对于A (3)对于B 5.判断以下十句话是正确的(打对号),错误的(打X),还是未知正确性(打?) P=NP 6.将以下各种类的关系用哈斯图表示出来 |
-- 作者:coolhunter -- 发布时间:7/5/2006 4:39:00 PM -- 我一道都不会做 |
-- 作者:w84u -- 发布时间:7/26/2006 2:53:00 PM -- 编译原理啊? |
-- 作者:galois -- 发布时间:8/21/2006 3:40:00 PM -- 貌似是很基本的东西。 |
-- 作者:suiyun0234 -- 发布时间:8/29/2006 11:53:00 AM -- 看不懂题目,说的是什么,谁能给个参考答案 |
-- 作者:yneversky -- 发布时间:1/24/2007 3:59:00 PM -- 第一题,即证明{0,1}*中的回文字符串(1)不是正则语言,(2)而是上下文无关语言
|
-- 作者:yneversky -- 发布时间:1/24/2007 5:57:00 PM -- 第一题的解答,以下说明中的 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是上下文无关语言. 证明第一部分(当), 即证如果x∈L(G) , 则 x∈L. 证明第二部分(仅当), 即证如果x∈L, 则 x∈L(G)
[此贴子已经被作者于2007-1-26 22:38:55编辑过]
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
7,230.469ms |