※ [本文转录自 NTU-Exam 看板 #1Kkwa6R8 ]
作者: irritum (働いたら 负け) 看板: NTU-Exam
标题: [试题] 103上 林智仁 自动机与形式语言 期末考+解答
时间: Sun Jan 18 20:37:22 2015
课程名称︰ 自动机与形式语言
课程性质︰ 必修
课程教师︰ 林智仁
开课学院： 电机资讯
开课系所︰ 资讯工程
考试日期（年月日）︰ 2015/1/6
考试时限（分钟）：
试题 :
‧ 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 other's class notes.
‧ Try to work on easier questions first.
Problem 1 (10 pts)
If we would like to prove
f(n) ≠ O(g(n)),
we need to show the opposite statement of the definition of
f(n) ＝ O(g(n)).
What is this oppsite statement ?
∀ c > 0, N ∈ N (自然数), ∃n ≧ N
such that f(n) > cg(n).
Problem 2 (25 pts)
Consider the following two functions
╭
f(n) ＝ │ n^3, if n is odd
│ n^2, if n is even
╰
╭
g(n) ＝ │ n^3, if n is prime
│ n^2, if n is composite
╰
Which of the following statements are true ?
(a) f ＝ O(n^2)
(b) f ＝ O(n^3)
(c) g ＝ O(n^2)
(d) g ＝ O(n^3)
(e) f ＝ O(g)
(f) g ＝ O(f)
(g) n^2 ＝ O(f)
(h) n^3 ＝ O(f)
(i) n^2 ＝ O(g)
(j) n^3 ＝ O(g)
You must prove the result of each sub-problem. If you think the statement is
false, you should prove the definition that you wrote for problem 1.
Statements (b),(d),(f),(g),(i) are true.
(a) For any c > 0, N ∈ N, we can let
n = an odd number larger than c and N.
Then
f(n) = n^3 > cn^2
→ f ≠ O(n^2)
(b) Let c = 1 and N = 1
cn^3 > n^2 ∀n ≧ N
→ cn^3 > f(n) ∀n ≧ N
→ f = O(n^3)
(c) For any c > 0, N ∈ N, we can let
n = a prime number larger than c and N.
Then
g(n) = n^3 > cn^2
→ g ≠ O(n^2)
(d) Let c = 1 and N = 1
cn^3 > n^2 ∀n ≧ N
→ cn^3 > g(n) ∀n ≧ N
→ g = O(n^3)
(e) For any c > 0, N ∈ N, we can let
n = an odd and composite number larger than c and N.
Then
f(n) = n^3 > cg(n) = cn^2
→ f ≠ O(g)
(f) Let c = 1 and N = 3
Because all of the prime numbers excepts 2 are odd,
cf(n) = cn^3 ≧ g(n) = n^3 , when n is prime and n≠ 2
and
╭
cf(n) ＝ │ cn^3
│ ≧ g(n) = n^2, when n is composite.
│ cn^2
╰
Therefore,
cf(n) ≧ g(n) ∀n ≧ N
→ g = O(f)
(g) Let c = 1 and N = 1
cn^3 ≧ n^2 ∀n ≧ N
→ cf(n) ≧ n^2 ∀n ≧ N
→ n^2 = O(f)
(h) For any c > 0, N ∈ N, we can let
n = an even number larger than c and N.
Then
n^3 > cf(n) = cn^2
→ n^3 ≠ O(f)
(i) Let c = 1 and N = 1
cn^3 > cf(n) = cn^2 ∀n ≧ N
→ cg(n) ≧ n^2 ∀n ≧ N
→ n^2 = O(g)
(j) For any c > 0, N ∈ N, we can let
n = a composite number larger than c and N
Then
n^3 > cg(n) = cn^2
→ n^3 ≠ O(g)
Problem 3 (20 pts)
f(n) O(f(n))
Assume g(n) ≧ n. Consider O(2 ) and 2 . Do we have
f(n)
g(n) ＝ O(2 )
O(f(n))
→ g(n) ＝ 2
or
O(f(n))
g(n) ＝ 2
f(n)
→ g(n)＝ O(2 )
(a) We will show that
g(n) = O(2^f(n))
→ g(n) = 2^O(f(n))
is true
Proof:
Since g(n) ≧ n and g(n) = O(2^f(n)), ∃c1 > 0, N1 ≧ 1, st.
c ≦ g(n) ≦ c1 * 2^f(n), ∀n ≧ N1, (1)
To prove that g(n) = 2^O(f(n)), we must prove that
g(n) ≦ c1 * 2^f(n) ≦ 2^(c2*f(n)), ∀n ≧N2 (2)
is true for some c2 > 0, N2 ≧ N1
Which means we should prove that ∃c2 > 1, N2 ≧ N1 s.t. ∀n ≧ N2.
log(c1) + f(n) ≦c2 * f(n)
→ f(n) ≧ log(c1)/(c2-1)
According to (1), we have
log n ≦ log(c1) + f(n)
→ f(n) ≧ log(n) - log(c1)
Therefore, we should prove that ∃c2 > 1, N2 ≧ N1 s.t.
log(n) - log(c1) ≧ log(c1)/(c2-1)
→ log(n) ≧ (c2/(c2-c1))*log(c1)
This is always true when n becomes large.
So given c1, N1, ∃c2 = 2, N2 = max{ N1, 4c1 }, such that (2) is
true.
Therefore, g(n) = 2^O(f(n))
(b) We will show that
g(n) = 2^O(f(n))
→ g(n) = O(2^f(n))
is not true.
Proof:
Let g(n) = 2^(2n), f(n) = n. Since
g(n) ≦ 2^(2*f(n)) for n ≧ 1,
we have
g(n) = 2^O(f(n)).
Assume g(n) = O(2^f(n)).
There are c > 0, N ≧ 1, such that ∀n ≧ N,
2^(2n) ≦ c * 2^n,
→ 2^(2n) ≦ c, ∀n ≧ N.
However, we can't find a constant c to satisfy 2^n ≦ c, ∀n ≧ N,
because the left side of the inequality goes to infinity when
n → ∞. Therefore there is a contradiction.
Problem 4 (20 pts)
Consider
f(n) ＝ log(1 + ε^n)
g(n) ＝ n
h(n) ＝ n^2
Which of the following statements are true ? For small-o, you can directly
calculate the limit without getting into the definition of limit.
(a) f(n) ＝ O(g(n))
(b) f(n) ＝ o(g(n))
(c) f(n) ＝ O(h(n))
(d) f(n) ＝ o(h(n))
Statement (a),(c),(d) are true.
(a) ∵ f(n) = log(1+ε^n) < log (2*ε^n) = log(2)+n ≦ 2*n, for n ≧ 1
∴ ∃c = 2, N = 1, s.t. ∀n ≧ N
f(n) ≦ cn
∴ f(n) = O(n) = O(g(n))
(b) According to L'Hospital Rule,
f(n) f'(n) e^n/(1+e^n) 1
lim ─── = lim ─── = lim ────── = lim (1 - ───) = 1
n→∞ g(n) n→∞ g'(n) n→∞ 1 n→∞ 1+e^n
Therefore, f(n) ≠ o(g(n))
(c) Since n^2 ≧ n, from sub-problem (a), ∃c = 2, N = 1 such that
f(n) ≦ cn ≦ cn^2, ∀n ≧ N.
Therefore, f(n) = O(h(n))
(d) According to L'Hospital Rule,
f(n) e^n/(1+e^n)
lim ─── = lim ────── = 0
n→∞ h(n) n→∞ 2n
Therefore, f(n) = o(h(n))
Problem 5 (5 pts)
Is the following language Turing recognizable ?
_
A_TM ＝ {〈M,w〉│〈M,w〉∈/ A_TM }, (ps. ∈/ : 不属于(打不出来))
where
A_TM ＝ {〈M,w〉│ M is a TM and accepts w}
It is not Turing recognizable.
We know that A_TM is Turing recognizable but undecidable. (Throrem 4.11)
_
Assume that A_TM is Turing recognizable.
Then A_TM is both co-Turing recognizable and Turing recognizable.
By Theorem 4.22 in the textbook, A_TM is decidable.
However, we have proved that A_TM is not decidable, so there is a
contradiction.
Problem 6 (20 pts)
Consider the following language
A ＝ {〈R,S〉│ R and S are regular expression and L(R) ⊆ L (S)}
Is it decidable?
Yes, it is decidable.
We first obseve that
L(R) ⊆ L(S) iff ∀w ∈ L(R), w ∈ L(S)
＿＿
iff ∀w ∈ L(R), w ∈\ L(S)
＿＿
iff L(R) ∩ L(S) = Φ
We can construct a DFA C such that
＿＿
L(C) = L(R) ∩ L(S)
with
1. The conversion of regular expression to an equivalant NFA
(procedure in Theorem 1.54).
2. Constructions for proving closure of regular languages under
complementation and intersection.
3. Conversion from NFA to DFA.
＿＿
We can then use Theorem 4.4 to test if L(C) = L(R) ∩ L(S) is empty.
The following TM F decides A:
On input〈R, S〉, where R and S are regular expressions.
1. Construct DFA C as described.
2. Run TM T from Theorem 4.4 on input〈C〉.
3. If T accepts, accept. If T rejects, reject.