[試題] 99上 林智仁 自動機與形式語言 期末考

[syuusyou (syuusyou)]

課程名稱︰自動機與形式語言
課程性質︰必修
課程教師︰林智仁
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰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
推 s864372002  :"bollow"
※ 編輯: syuusyou        來自: 140.112.214.43       (01/11 17:04)
→ syuusyou    :fixed，音太像拼錯XD