※ [本文轉錄自 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