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