課程名稱︰ 自動機與形式語言 課程性質︰ 資工系必修 課程教師︰ 林智仁 開課學院： 電機資訊學院 開課系所︰ 資訊工程學系 考試日期（年月日）︰ 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