课程名称︰ 自动机与形式语言 课程性质︰ 资工系必修 课程教师︰ 林智仁 开课学院： 电机资讯学院 开课系所︰ 资讯工程学系 考试日期（年月日）︰ 2009/01/15 考试时限（分钟）： 90分钟 是否需发放奖励金： 是，谢谢 （如未明确表示，则不予发放） 试题 : 1.(15%) Explain if the following description is correct or not. Let Σ be the alphabet of a Turing machine. We consider any binary sequence such as 10101111... Any such sequence is in Σ*. Using the diagonalization method, the set of all infinite binary sequseces is countale. Therefore, Σ* is uncountable. 2.(15%) We define Primality = {n 属於 N | n is a prime}. Explain is the following description is correct or not. We can test whether a number n is a prime by dividing n by 1,2,3,...,√(n) √(n) = n^(1/2) = O(n^2). Therefore Primality 属於 P. 3.(15%) Is EQ(DFA) 属於 P or not? 4.(20%) Answer if the following statement is correct or not. Explanation is needed. You cannot just say yes or no. (a) If f(n) = 2^(O(t(n))), then [f(n)]^2 = 2^(O(t(n))). (b) If f(n) = o(2^(2n)), then f(n) = o(2^n). 5.(15%) We know that small-o notation is defined in the following way : f(n) = o(g(n)) if f(n) lim------------- = 0. n->∞ g(n) From the definition of limit, this means 对於所有 c ﹥0, 存在一个 N, 对於所有的 n ≧ N, f(n) ==> ---------- < c. g(n) If f(n) = n and g(n) = 3^n, how do you find N to make the above statement correct? ─ 6.(15%) We define co-NP = { L = L 属於 NP}. Is Primality 属於 co-NP ? You can not use the fact 〝Primality 属於 P〞 in your explanation. 7. (a) (5%) Calculate 5281 X 77773 = ? (b) (Bonus 5%) p ≦ q are primes and p X q = 203447, find p and q. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.91.80