[試題] 98上 林智仁 自動機與形式語言 期末考
課程名稱︰自動機與形式語言
課程性質︰資訊系大三必修
課程教師︰林智仁
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰2010/01/12
考試時限（分鐘）：三小時(有點忘了@@)
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Problem 1(25%)
Assume the input string is always a*b*. Construct a two-tape Turing machine
with no more than 3 states to handle the language { a^n b^n | n >= 0 }. The
running time must be no more than O(n). Simulate a^4 b^4.
You need to give a formal definition though the δ table can de omitted. A
diagram is needed. Links to qr can be omitted. Following the formal definition
of multi-tape TM in the textbook (p.150), we allow the head to stay put. That
is,
δ: Q ×Γ^k →Q ×Γ^k ×{L, R, S}
Problem 2(20%)
1. Extend multi-tape TM and NTM to multi-tape NTM. Give a reasonable
definition.
2. Use a multi-tape NTM with no more than 4 states to handle the language
{ ww^R | w 屬於 {0, 1}* }
You need to give a formal definition though the δ table can de omitted. A
diagram is needed. Links to qr can be omitted. Similiar to problem 1, we allow
the head to stay put.
Problem 3(10%)
Let A = { <R> | R is a regular expression describing a language contain at
least once string w that has 111 as a substring(i.e., w = x111y for some x and
y)}. Prove or disprove that A is decidable.
Problem 4(20%)
Given a positive function f(n). Prove or disprove the following statement
If f(n)^0.5 = O(2^n), then f(n) = O(2^n).
You need to give a formal prove.
Problem 5(20%)
We know that small-o 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
f(n)
for all c > 0, exist N, for all n ≧ N, ─── < c
g(n)
If f(n) = 2^n ans g(n) = n,
prove f(n) ≠ o(n) using the opposite statement of (2).
Problem 6(5 or 15%)
1. (5%) Calculate 2010 ×528825
2. (Bonus 10%) Find 17111687 = p ×q, where p, q > 1.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.121.223