※ [本文轉錄自 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/m.aspx?n=bbs/NTU-Exam/M.1446122770.A.3C5.html

※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: w4a2y4 (220.134.213.196), 10/15/2017 12:36:33