※ [本文转录自 NTU-Exam 看板 #1GlUsQUs ] 作者: rod24574575 (天然呆) 看板: NTU-Exam 标题: [试题] 101上 林智仁 自动机与形式语言 期中考2 时间: Tue Dec 4 20:33:27 2012 课程名称︰自动机与形式语言 课程性质︰必修 课程教师︰林智仁 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰2012.12.4 考试时限（分钟）：135分钟 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题： ˙ 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 (20pt) Consider the following NFA. ┌─┐ 1 ┌─┐0,1,ε┌─┐0,1,ε╔═╗ start ─→│q1│──→│q2│──→│q3│──→║q4║ └─┘ └─┘ └─┘ ╚═╝ ↑│ └┘0,1 1. Find a CFG with no more than 7 rules for this language. 2. Find a PDA with no more than 4 states for this language. Give the formal definition and the state diagram. Problem 2 (25pt) Consider the following language n n {0 1 │n≧0}. 1. What is the PDA with the smallest number of states such that it has a single accept state? 2. Use the method taught in the class to simulate the input string 000111 by drawing a tree. 3. Modify the PDA in 1 to satisfy all conditions needed in lemma 2.27 and produce CFG rules. Problem 3 (5pt) Let Σ = {0, 1}. Give a PDA with the smallest number of states such that it may accept strings when the stack is not empty. Problem 4 (10pt) Please design an one tape Turing machine with no more than 5 states (including q_a and q_r) that shifts the input to the right for one position. For example, 0101 becomes ∪0101. Let Σ = {1, 0}. You need only draw the state diagram. Links to q_r are not needed. Problem 5 (40pt) Consider the following language n 2n {0 #0 │n≧0}. 1. (5%) Give a CFG with no more than 2 rules for this language. 2. (5%) Construct a PDA with no more than 5 states for this language. 3. (15%) Construct a Turing machine with no more than 9 states (including q_a and q_r) for this language. Links to q_r are not needed. 4. (15%) Construct a 2-tape Turing machine with no more than 5 states (including q_a and q_r) for this language, and simulate the string 00#000. Links to q_r are not needed. Note that the transition function δ of multitape Turing machine is k k Ｑ × Γ → Ｑ × Γ × {Ｌ,Ｒ,Ｓ} , where k is the number of tapes. --

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

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: w4a2y4 (140.112.25.121), 11/30/2017 17:08:43