湖南大学计算理论引论期末试题计算理论考试题_湖南大学期末考试试卷

湖南大学计算理论引论期末试题计算理论考试题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“湖南大学期末考试试卷”。

计算理论试题

说明：本试卷共5题，每题20分，满分100分。

1如果L1，L2为正则语言，证明L1•L2是上下文无关语言；如果L1为正则语言，L2是上下文无关语言，试举反例说明证明L1•L2是不是上下文无关语言

（编者提示：设计一个pda即可证明；L1为an，L2为bncn（n为上标），则L1•L2不是上下文无关语言，用上下文无关文法的泵引理证明即可

2.设语言{an bncmam bkck|m，n，k为正整数}（编者：n,m,k为上标）

（1）给出上述语言的上下文无关文法

（2）给出上述语言的下推自动机

3．证明：若L 可被一NTM M1识别, 则必被一DTM M2 识别.4．设上下文无关文法G, 将下述CFG转换为乔姆斯基文法。

G:

SASB |

AaAS|a

BSbS|A|bb1)6个人组成的一个集团，试证明：或者3个人相互认识，或者3个人相互不认识。

2)给定k个整数的一个列表i1, i2,…,ik，能否将这些整数分成总和相等的两个集合？试指出该问题属于P或者NP,并给出相应算法。