課程名稱︰自動機與形式語言 課程性質︰系必修 課程教師︰項潔 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰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