作者syuusyou (syuusyou)
看板NTU-Exam
标题[试题] 99上 林智仁 自动机与形式语言 期末考
时间Tue Jan 11 12:57:01 2011
课程名称︰自动机与形式语言
课程性质︰必修
课程教师︰林智仁
开课学院：电资学院
开课系所︰资讯系
考试日期（年月日）︰2011/01/11
考试时限（分钟）：120 (10:30~12:30)
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
- Please give details of your calculation. 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.
- This is the final exam of Prof. Chin-Jen Lin's Introduction to the Theory
of Computation. If you take Prof. Jieh Hsiang's class, please go to R104.
Problem 1 (30 pts)
Give an example of f and g such that
(a) f, g are not polynomials
(b) f = O(g)
(c) f = o(g)
Problem 2 (30 pts)
Let
C_RE = { <R,K> | R is a regular expression. L(R) contains exactly k strings
where k >= 0 or k = inf. }.
Is this language decidable?
Problem 3 (30 pts)
Define
f(n) = 2 ^ o(g(n))
if
lim (log2(f(n))/g(n)) = 0
n->inf
Prove or disprove the following statements:
(a) f(n) = 2 ^ o(g(n))
is equivalent to
f(n) = o(2^g(n))
(b) f(n) = 2 ^ O(g(n))
is equivalent to
f(n) = O(2^g(n)).
Problem 4 (10 or 40 pts)
(a) (10 pts) Calculate 2,011 * 530,528
(b) (Bonus 30 pts) Find 55,983,881 = p * q, where p, q > 1 and p, q belongs
to N.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.214.43
1F：推 s864372002 :"bollow" 01/11 14:56
※ 编辑: syuusyou 来自: 140.112.214.43 (01/11 17:04)
2F：→ syuusyou :fixed，音太像拼错XD 01/11 17:04
3F：→ andy74139 :已收录至!! 01/11 18:34