湖南大学计算理论引论期末试题计算理论考试题|引论|考试题-人人范文网

计算理论试题

说明：本试卷共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转换为乔姆斯基文法。

SASB |

AaAS|a

BSbS|A|bb

5 1)6个人组成的一个集团，试证明：或者3个人相互认识，或者3个人相互不认识。

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