※ [本文转录自 NTU-Exam 看板 #1IrXGvBE ]
作者: ibetrayall () 看板: NTU-Exam
标题: [试题] 102上 林智仁 自动机与形式语言 期末考
时间: Wed Jan 15 12:53:10 2014
课程名称︰自动机与形式语言
课程性质︰必修
课程教师︰林智仁
开课学院：电资学院
开课系所︰资讯系
考试日期（年月日）︰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。