※ [本文转录自 NTU-Exam 看板 #1IYlb7Nb ] 作者: ibetrayall () 看板: NTU-Exam 标题: [试题] 102上 林智仁 自动机与形式语言 期中考2 时间: Tue Nov 19 13:38:12 2013 课程名称︰自动机与形式语言 课程性质︰ 课程教师︰林智仁 开课学院：电资学院 开课系所︰资讯工程系 考试日期（年月日）︰102/11/19 考试时限（分钟）：10:25 ~ 13:25 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : ‧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 athers' class notes. ‧Try to work on easier questions first. Problem 1 (10 pts) Consider the following PDA. ε,ε → $ ─┐ 0,ε → 0 start →《q1》─────→ q2 │ ←┘ 1,ε → 0 │ │ ε,ε → $ │ ↓ ─┐ 0, 0 → ε 《q4》←───── q3 │ ←┘ 1, 1 → ε ε,$ → ε Problem 2 (10 pts) Consider the following grammar with Σ = {a,b}. S → ASB A → SA | AB | a | ε B → SBS | A | bb | ε Find the Chomsky normal form. You must show details of the procedure and follow the order of steps below. ‧add S_0 → S ‧remove V → ε ‧remove V_1 → V_2 Problem 3 (80 pts) Consider Σ = {0,1} and A = { w | w ∈ Σ* and has an even number os 0s}. Please answer the following questions. (a) (5 pts) Draw a 2-state DFA diagram for this language. (b) (5 pts) Follow the way described in our lecture to have a 5-rule CFG for this language. The main idea is that if DFA has δ(p,a) = q, then we add a rule S_p → aS_q. (c) (15 pts) Does this CFG has the smallest number of rules? If yes, explain why. If not, give a CFG with the smallest number of rules. Please prove that the CFG you gave has the smallest number of rules. Note: the proof may be a little bit difficult. You may work on subsequent sub-problems first. (d) (10 pts) For CFG obtained in (b), obtain a PDA using the procedure in our proof of the equivalence between PDA and CFG. (Lemma 2.21) (e) (10 pts) The PDA obtained in (d) apparently does not have the smallest number of states . Give a PDA with only two states for this language. You don't need to give the formal definition. A state diagram is enough. (f) (10 pts) Modify the PDA obtained in (e) to satisfy the following conditions needed in Lemma 2.27: - It has a single accept state, q_accept. - It empties its stack before accepting. - Each transition either pushes a symbol onto the stack (a push move) or pops one off the stack (a pop move), but it does not do both at the same time. We require you to use three states and no more than six edges in your answer. The one pointing to the start state is not counted as an edge. You must explain why for your answers these conditions are satisfied. Hint: you may need to adjust your answer for (e). (g) (10 pts) Use the PDA obtained in (f) to generate the corresponding CFG by method in Lemma 2.27. (h) (5 pts) Check if you can use the CFG obtained in (g) to generate the following strings: - 0011 - 01000 (i) (10 pts) Design a DPDA for this language with the smallest number of states. You are required to give its formal definition. Note that in drawing PDAs, you CANNOT use the shorhand like q0 │ │ a, s → xyz ↓ q1 注：被《》括住的代表 accept state 。 --

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

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