※ [本文转录自 NTU-Exam 看板 #1IrXGvBE ] 作者: ibetrayall () 看板: NTU-Exam 标题: [试题] 102上 林智仁 自动机与形式语言 期末考 时间: Wed Jan 15 12:53:10 2014 课程名称︰自动机与形式语言 课程性质︰必修 课程教师︰林智仁 开课学院：电资学院 开课系所︰资讯系 考试日期（年月日）︰102/12/31 考试时限（分钟）：10:20 ~ 12:50 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : ‧Please give details of your answer. 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. Problem 1 (10 pts) Design a Turing machine to shift the input w to ∪w. Assume Σ = {0,1}. Give the formal definition as well as the state diagram. This has been an exam problem in the past. However, because many asked this question, we decide to put it as an exam problem again. Problem 2 (25 pts) Assume Σ = {0}. In our lecture, we design a two-tape machine so that given a string w, we first check if w∈{0^2n|n>=0}, and then generate ww in the end. Now we would like to generate www instead. a. Can you use a three-tape (deterministic) machine with no more than four states (including the reject state) to do this task? Note that if w/∈{0^2n|n>=0}, then your machine should reject it. Following the textbook, here we assume the head of a multitape Turing machine has the ability to stay put. That is, δ:Q ×Γ^k → Q ×Γ^k ×{L,R,S}^k. Also note that in our lecture we assumed there is an empty symbol (i.e.,∪) at the beginning. Here we DO NOT have such assumption. Namely, the initial contents of the three tapes are: w_1w_2‧‧‧∪∪∪‧‧‧ ∪∪∪‧‧‧ ∪∪∪‧‧‧ In your diagram, you don't need to show links to q_r. b. Simulate the input strings 0000 and 000. Hint: You can introduce other tape characters. This problem is not easy, so you can do others first. Problem 3 (15 pts) Consider Σ={0,1} and the following language. {w|w has an even number of 0's or an even number of 1's} Design a deterministic Turing machine with no more than six states (including the reject state) for this language. You only need to draw the state diagram. In your diagram, you don't need to show links to q_r. Problem 4 (10 pts) Is the following language TM-decidable? Please give a brief explaination. L = {n|n is a prime number} Problem 5 (10 pts) _ If a language L is decidable, is its complement L decidable too? If YES, prove your answer; if NOT, give a counter example. Problem 6 (20 pts) Define f(n) = logO(g(n)) if and only if there are c and N such that f(n) <= log(cg(n)), ∀n >= N. 1. Is log(3^n) = logO(2^n)? 2. Is log(3^n) = 2^logO(n)? 3. Is log(n^2) = logO(n)? Problem 7 (10 pts) Is sin(n) = o(cos(n))? Prove your answer by formal definition of small-o. You need to give details by getting into the definition of limit. 附注： log 可以是 log_10 或 ln，但绝对不是 log_2。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.70.230.196

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: w4a2y4 (140.119.121.6), 01/05/2018 16:46:23