※ [本文轉錄自 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.