课程名称︰自动机与形式语言 课程性质︰必修 课程教师︰林智仁 开课学院：电机资讯学院 开课系所︰资讯工程学系 考试日期（年月日）︰107.12.3 考试时限（分钟）：160 试题 : Introduction to the Theory of Computation Midterm 2 December 3, 2018 10:20-13:00 ● Please write your answers in English. ● Please give details of your answers. A direct answer without explanation is not ciunted. ● Read the problem statements carefully. ● During the exam, you are not allowed to borrow others' notes. ● The problems may not be ordered according to difficulty. Try to work on easier problems first. Problem 1 (10 pts). Transform the following CFG to Chomsky Normal Form(CNF). S→00S|0A|1A A→11A|ε Problem 2 (35 pts). Consider the language L = {ww^R|w∈{0, 1}*}, where w^R denotes the reverse of w. (a) (5 pts) In th lecture/textbook we showed a 4-state PDA for L as follows. ε, ε→$ ─┐ 0, ε→0 →q1─────→q2←┘ 1, ε→0 │ │ε, ε→$ │ ↓ (q4)←─────q3─┐ 0, 0→ε ε,$ → ε ←┘ 1, 1→ε Draw the trees of running ● 0110 ● 1010 You need to show all nodes that can be reached by ε links. (b) (10 pts) For the language L, give a CFG with one variable and 3 rules. Explain in detail why it has the smallest number of rules. (c) (10 pts) For the CFG obtained in (b), generate a corresponding PDA with the procedure in Lemma 2.21 of the textbook. Draw the tree of running 0110. You need to show all nodes that can be reached by ε links. Hint: There must be at least 25 nodes; otherwise it is wrong. (d) (10 pts) Now we would like to generate a corresponding CFG with the procedure in Lemma 2.27 of the textbook. There are three required feature for the PDA: (i) It has a single accept state. (ii) It empties its stack before accepting. (iii) Each transition either pushes one symbol onto the stack or pops one off the stack, but not both at the same time. Dose the PDA in (a) satisfy all of them? If so, briefly show why each requirement is satisfied. If not, give a PDA with no more than 5 states satisfying the requirements. You are NOT allowed to change Σ or Γ. Than generate the corresponding CFG and give its formal definition. Problem 3 (30 pts). Consider the following NFA for the language M described by the regular expression (01)* 0 ─────→ →(q1) q2 ←───── 1 (a) (10 pts) Give a CFG with one variable and the smallest number of rules for M. We further require that the total lengths if the rules is minimized. Explain why yours satisfies this requirement. (b) (10 pts) Now we modify the edges of the NFA to make it become the following PDA. 0, ε→ε ─────→ →(q1) q2 ←───── 1, ε→ε Does the PDA satisfy all the requirements in Lemma 2.27? If not, give a modified PDA with Γ = {0} to meet the requirements. Then apply the procedure in Lemma 2.27 to generate a CFG for M. You may use A_ij to represent A_qi,qj for simplicity. (c) (10 pts) From the CFG obtained in (b), extract a small subset of no more than 7 rules, then further simplify these rules to your solution in (a). Hence this procedure shows that the subset of rules you choose can generate M. Hints: ● You may need to apply similar techniques for transforming a CFG to CNF. ● At some point you may need to extract several rules again in order to generate your solution in (a). ● You may need to use the fact that the sets of rules in (a) and (b) both generate M. Problem 4 (25 pts). Consider the language {w$|w∈{0, 1}*, #0(w) = #1(w)}, where #i(w) is the number of occurences of i in w. (a) (10 pts) Design a PDA with no more than 3 states for this language. We further require that Γ={0, 1, $}. Explain why it is not a deterministic PDA (DPDA). (b) (15 pts) Design a DPDA with at most 8 states for this language. We still require that Γ = {0, 1, $}. Hint: To avoid non-determinism, you may transform a transition ε to two. Simulate and draw the trees of running ● 0011$ ● 1$ -- 在很久的以後 你是否记得我 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.150.17 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1543942427.A.C08.html