課程名稱︰自動機與形式語言 課程性質︰系必修 課程教師︰林智仁 開課學院：電資學院 開課系所︰資訊系 考試日期（年月日）︰101/1/10 考試時限（分鐘）：60 是否需發放獎勵金：是, 謝謝 （如未明確表示，則不予發放） 試題 : 1. (20pts) We say w1 is w2's subsequence if we can obtain w1 by removing some symbols in w2. For example, ad is a subsequence of abcbc by removing the second, the third, and the fifth symbols. As a result, εis a subsequence of any string. Is A = {(C,w)|C is a CFG which can generate at least 1 subsequence of w^k for some k} Turing decidable? If you use any lemma which is not taught in the class, even if it is in the textbook, you need to prove it. This problem can be solved without using any lemma which is not taught. 2. (20pts) Assume f1(n) = O(2^n) and f2(n) = O(3^n) Is f1(n) + f2(n) = O(3^n)? 3. (30pts) Assume f1(n) = O(2^n) and f2(n) = o(3^n) Is f1(n) + f2(n) = o(3^n)? 4. (20pts) Prove whether the following two statements are true or false (a) If A and B are countable, then A∪B is also countable (b) All irrational numbers are not countable. 5. (5pts or -10pts) In Chapter 7 (or in the lecture last week) we mentioned one of the greatest unsolved computer science problem. What is it? If you correctly answer this question, you get 5 points. Otherwise, -10. 6. (5 or 25 pts) (a) (5pts) Calculate 48,023 × 89,363 (b) (Bonus 20 pts) Find 512,973,211 = p × q, where p,q>1 and p,q ∈N. --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.193.169