※ [本文转录自 NTU-Exam 看板 #1MCXKIF5 ] 作者: eddy1021 (eddy) 看板: NTU-Exam 标题: [试题] 104上 林智仁 自动机与形式语言 期中考1 时间: Thu Oct 29 20:46:07 2015 课程名称︰ 自动机与形式语言 课程性质︰ 资工系大三必修 课程教师︰ 林智仁 开课学院： 电机资讯学院 开课系所︰ 资讯工程学系 考试日期（年月日）︰ 2015/10/27 考试时限（分钟）： 135分钟 试题 : ● Please give details of your answer. A direct answer without explanation is not counted. ● Your answer 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(35 pts) 1.(5 pts)Consider the following language of having only one string: A = {a}. Assume Σ= {a}. What is the NFA diagram with the smallest number of states for this language? Give the formal definition. You need to prove yours has the smallest number of states. 2.(5 pts)If Σis changed to Σ= {a,b}, what are the new diagram and the new formal definition? 3.(5 pts)Now consider the language A = {a,b}. Assume Σ= {a,b}. What is the NFA with smallest number of states for this language? No need to give the formal definition. You need to argue yours has the smallest number of states. 4.(10 pts) Use the procedure in the textbook to convert the NFA in 1.3 to DFA. Reduce it to have the smallest number of states. No need to give the formal definition. You need to explain yours has the smallest number of states. 5.(5 pts) For the same language, we consider {a,b} = {a} U {b}. For {a} and {b}, we can have two NFA diagrams for them from 1.1. Consider the way in Theorem 1.45 of textbook to do union of two NFA. What are the resulting diagram and the formal definition? 6.(5 pts) Convert the above NFA diagram to DFA. If the number of states is too many, you need to explain why some are not necessary so you don't draw them. Reduce the DFA to the smallest number of states. Is the resulting DFA the same as that of 1.4? Problem 2(35 pts) Consider the following two language. Let Σ= {0,1}. W0 = { w | w ends with 0 } (e.g., 000, 100, 11010) W1 = { w | w ends with 1 } (e.g., 111, 001, 01101) 1.(5 pts) Give a DFA of two states for each of the above languages. Then, use the technique described in textbook chapter 1.3 to generate an NFA for W0 o W1. 2.(5 pts) Use the procedure in textbook chapter 1.2 to convert 2.1 to a DFA. 3.(5 pts) Give the regular expression for W0 o W1. The number of the characters(including \intersection,\union,(,),* but not o,{,} ) should be ≦15. 4.(10 pts) Consider the DFA in 2.2. Use the procedure in textbook chapter 1.3 to get a GNFA and obtain a regular expression. Can you explain that it is equivalent to that of 2.3? 5.(10 pts) If we consider the NFA in 2.1 and apply the same procedure in 2.4, what is the resulting regular expression? Is the result equivalent to that of 2.4? Assume your NFA in 2.1 has 4 states q1,...,q4 from left to right. Use the order of q4, q3, q2, q1 to remove states. Problem 3(30 pts) 1.(15 pts) Let Σ= {a,b,c} D = { w | w contains the same number of substrings ab, bc, ca, but does not contain substring like ac, cb, ba } Is D a regular language? Prove or disprove it. 2.(15 pts) Let Σ= {a,b,c} D = { w | w contains the same number of substrings ab, bc, ca, ac, cb, ba } Is D a regular language? Prove or disprove it. ================================== 试题完 =================================== --

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

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: w4a2y4 (220.134.213.196), 10/15/2017 12:36:33