课程名称︰自动机与形式语言 课程性质︰系必修 课程教师︰项洁 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰2012/1/10 考试时限（分钟）：180 是否需发放奖励金：是 感谢 （如未明确表示，则不予发放） 试题 : 1.(a)Show that the set of all infinite sequences over{0,1} is uncountable. (b)Show that {0,1}* is countable. 2.Show that {<R,S>:R and S are regular expressions and L(R)包含於L(S)} is decidable. 3.Show that there exists some undecidable language L that is mapping _ reducible to its complement, i.e.,L ≦m L. 4.(a)Use Rice's theorem to show that {<M>: M is a TM and L(M)=Σ*}. (b)Consider the problem of determining whether a single-tape Turing machine ever writes a blank symbol over a nonblank symbol during the course of its computatoin on any input string. Show that this problem is undecidable without using Rice's theorem. 5.Show that P is closed under union, concatenation, and complement. 6.Every rule in a regular grammar is of the form: (i)A->a, (ii) A->aB,or (iii)A->ε, where A and B are non-terminals and a is a terminal.Show that a language L is regular if and only if some regular grammar generates L. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.52