課程名稱︰計算理論
課程性質︰選修
課程教師︰顏嗣鈞
開課學院：電資學院
開課系所︰電機系
考試日期（年月日）︰2012/01/09
考試時限（分鐘）：9:10 ~ 12:00
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Theory of Computtaion
Final Exam,January 9, 2012
1.(20 pts) True or false? No explanations needed.
Score＝max{0,Right－1/2 Wrong}
(a)
If L⊆0^* , then L is always recursive.
(b)
If L <=_m {0^n 1^n | n>= 0},then L is recursive.
(c)
{0^n 0^2n 0^3n |n >= 0} is context-free but not regular.
(d)
{xωx^R|x,ω∈{0,1}^+} is context-free but not regular.
(e)
{ωa^n a^n ω^R |ω∈{a,b}^* ,n>0} is context-free but not regular.
(f)
{a^n b^(n^2)|n >= 0} is not context-free.
(g)
u is a subsequence of v if u can be obtained by dropping symbols from u ,
where u,v ∈Σ^* . For example 11,011 are sequences of 1002.If A is
context-free,then SUBSEQ(A) = {u | ∃u∈A such that u is a subsequence of v}
is also context-free.
(h)
The language {< G > |G is context-free grammar and G is ambiguous} is
recursively enumerable(r.e.).
(i)
The language {< M ,ω> | M is a linear bounded automaton and M accepts ω}
is not recursive.
(j)
The language L = {< G,D > | G is a context-free grammar,D is a regular grammar}
, and L(G)⊆L(D)} is recursive.
2.
(20 pts) For the following languages , determine whether the language is
(A) recursive , (B) recursively enumerable but not recursive,
(C)not recursively enumerable. No explanations needed.No penalty for wrong
answers.
(a)
L_1 = {< M > | M is a TM and there exists an input on which M halts in less
than |< M >| steps}
(b)
L_2 = {< M > | M is a TM that accepts all even numbers}.
(c)
L_3 = {< M > | M is a TM and L(M) is finite}.
(d)
L_4 = {< M > |M is a TM and L(M) is infinite}.
(e)
L_5 = {< M > | M is a TM and L(M) is an uncountably infinite set}.
(f)
L_6 = {<M_1,M_2> |M_1,M_2 are TMs and ε∈L(M_1)∪L(M_2)}.
(g)
L_7 = {<M_1,M_2> | M_1,M_2 are TMs and ε∈L(M_1)∩L(M_2)}.
(h)
L_8 = {< M_1 ,M_2 >}M_1 , M_2 are TMs and ε∈L(M_1)－L(M_2)}.
(i)
L_9 = {< M > |M is a TM, and there exists an input whose length is less than
100 on which M halts}
(j)
L_10 = {< M >| M is a TM and M is the only TM that accepts L(M)}
3.(10 pts)Consider the following grammar:
S → AB|BC A → AB|a B → CC|b C →BA|b
Apply the CYK algorithm to determine whether the string ababa is generated
by the grammar. Yoy need to draw the CYK table to show the computation.
4.(10 pts)For a language L⊆Σ^* , define reflect (L) = {ωω^R | ∃ω∈ L}
where ω^R donotes the reverse of the string ω.
(a)
(4 pts) Consider L_0 = {0^i 1^i | i >= 0} and L_1 = 0^* 1^*.
What are reflect (L_0) and reflect (L_1)?
(b)
(6 pts) Is the class of context-free languages closed under reflect ?
Justify your answer.
5.
(10 pts) Prove that the language L = {a^i b^j c^k |j<i , j<k} is NOT
context-free.
6.
(10 pts)For any language L⊆Σ^* , and any u∈Σ^* , let u/L =
{v∈Σ^* | un∈L}. Prove that if L is context-free , then u/L is also
contexr-free for every u∈Σ^*.
(Hint: let u=a_1 ．．．a_k , for some k , and let M = (Q,Σ,Γ,δ,q_0,Z_0,F)
be a PDA accepting L.Construct a PDA M' to accept u/L.)
7.
(4 pts) Define context-sensitive grammars.
8.(10 pts) Let A , B ⊆ {0,1}^* be r.e. languages such that A∪B={0,1}^*
and A∩B≠Φ. Prove that A <=_m (A∩B),where <=_m denotes the many-one
reduction.
(Hint: Let M_1 be a TM accepting A and M_2 be a TM accepting B.
Further , since we know that A∩B ≠Φ , we know that some string y will be
accepted by both M_1 and M_2. Construct a mapping f that witnesses <=_m,
i.e., x∈ A ⇔ A∩B.)
9.
-
(6 pts) Suppose A is recursively enumerable and A<=_m A .
Prove that A is recursive.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.25.106