课程名称︰自动机与形式语言 课程性质︰资讯系大三必修 课程教师︰林智仁 开课学院：电机资讯学院 开课系所︰资讯工程学系 考试日期（年月日）︰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