課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰林智仁
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰102/12/31
考試時限（分鐘）：10:20 ~ 12:50
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
‧Please give details of your answer. A direct answer without explanation is
not counted
‧Your answers must be in English.
‧Please carefully read problem statements.
‧During the exam you are not allowed to borrow others' class notes.
‧Try to work on easier questions first.
Problem 1 (10 pts)
Design a Turing machine to shift the input w to ∪w. Assume Σ = {0,1}. Give
the formal definition as well as the state diagram. This has been an exam
problem in the past. However, because many asked this question, we decide to
put it as an exam problem again.
Problem 2 (25 pts)
Assume Σ = {0}. In our lecture, we design a two-tape machine so that given
a string w, we first check if w∈{0^2n|n>=0}, and then generate ww in the end.
Now we would like to generate www instead.
a. Can you use a three-tape (deterministic) machine with no more than four
states (including the reject state) to do this task? Note that if
w/∈{0^2n|n>=0}, then your machine should reject it. Following the textbook,
here we assume the head of a multitape Turing machine has the ability to stay
put. That is,
δ:Q ×Γ^k → Q ×Γ^k ×{L,R,S}^k.
Also note that in our lecture we assumed there is an empty symbol (i.e.,∪)
at the beginning. Here we DO NOT have such assumption. Namely, the initial
contents of the three tapes are:
w_1w_2‧‧‧∪∪∪‧‧‧
∪∪∪‧‧‧
∪∪∪‧‧‧
In your diagram, you don't need to show links to q_r.
b. Simulate the input strings 0000 and 000.
Hint: You can introduce other tape characters. This problem is not easy, so
you can do others first.
Problem 3 (15 pts)
Consider Σ={0,1} and the following language.
{w|w has an even number of 0's or an even number of 1's}
Design a deterministic Turing machine with no more than six states (including
the reject state) for this language. You only need to draw the state diagram.
In your diagram, you don't need to show links to q_r.
Problem 4 (10 pts)
Is the following language TM-decidable? Please give a brief explaination.
L = {n|n is a prime number}
Problem 5 (10 pts)
_
If a language L is decidable, is its complement L decidable too?
If YES, prove your answer; if NOT, give a counter example.
Problem 6 (20 pts)
Define
f(n) = logO(g(n))
if and only if there are c and N such that
f(n) <= log(cg(n)), ∀n >= N.
1. Is
log(3^n) = logO(2^n)?
2. Is
log(3^n) = 2^logO(n)?
3. Is
log(n^2) = logO(n)?
Problem 7 (10 pts)
Is
sin(n) = o(cos(n))?
Prove your answer by formal definition of small-o. You need to give details by
getting into the definition of limit.
附註：
log 可以是 log_10 或 ln，但絕對不是 log_2。