※ [本文轉錄自 NTU-Exam 看板 #1KkrPdqp ] 作者: irritum (働いたら 負け) 看板: NTU-Exam 標題: [試題] 103上 林智仁 自動機與形式語言 第一次期中考 時間: Sun Jan 18 14:44:48 2015 課程名稱︰ 自動機與形式語言 課程性質︰ 必修 課程教師︰ 林智仁 開課學院： 電資學院 開課系所︰ 資訊工程 考試日期（年月日）︰ 2014/10/28 考試時限（分鐘）： 試題 : ‧Please give details of your calcultatoin. 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 other's class notes. ‧Try to work on easier question first. Problem 1 (25%) 1. Consider the following language of having only one string: {a} Assume Σ = {a}, what is the DFA diagram with the samllest number of states for this language ? Give the formal definition. 2. Prove why yours has "the smallest number of states" ? 3. Now consider two languages: A = {a}, with Σ_A = {a}, B = {b}, with Σ_B = {b}, We would like to prove that A∪B is regular. Before introducing DFA, in our lecture (or in the textbook), we construct a DFA with states like (q,r), where q is from that of the first machine and r is from the other. However, in that construction, we assume that A and B have the same Σ. Please modify your DFA for A in 1., so that it handles the language : {a}, with Σ = {a,b} 4. After 3., we can use a similar setting for {b}, with Σ = {a,b}. Then use the procedure in our lecture to construct a DFA for A∪B. 5. Give a DFA with the smallest number of states for A∪B. Can you reduce the DFA in 4. to your DFA here? Problem 2 (15%) Consider the following regular expression (a∪b)* Assume Σ = {a,b} 1. What is the DFA with the smallest number of states for this language ? 2. Starting with the following NFA. ┌─┐ a, b ╔═╗ start →│q1│───→║q2║ └─┘ ╚═╝ Use the procedure in the text book to prove that A* is regular to generate a three-state NFA. Let's follow the textbook to have ε-links from the accept states to the original start state. Give the formal definition of this three-state NFA. 3. Convert the three-state NFA to an eight-state DFA by using the power set of NFA's states as the new set of states. Can the eight-state DFA be simplified to the DFA obtained in 1. ? Problem 3 (20%) Consider the following state diagram: 1 ╔═╗←───╔═╗ 0 ╔═╗ 1 ┌─┐ start →║q1║ ║q2║───→║q3║───→│q4│ ╚═╝───→╚═╝ ╚═╝ └─┘ ↑│ 0 ↑│ ↑│ └┘ └┘ └┘ 1 0 0,1 1. (5%) What is the language of this DFA ? 2. (8%) Modify this DFA to GNFA and find the regular expression of the language. Please follow the order q1, q2, q3, q4 to remove states. 3. (7%) Can you see that the results in 2. correspond to the language described in 1. ? Prove it ! Problem 4 (20%) 1. Assume L is regular. Is the following language regular ? _ R L = { w | w ∈ L of w ∈ L } R where w is the reverse of w. Please prove your answer. 2. Is the following language regular ? n! L = { a | n ≧ 0 } Please prove your answer. Problem 5 (20%) In our proof of that n n A = { 0 1 | n ≧ 0 } is not regular, we demonstrate that we can use only two of the three consditions : i i. x y z ∈ A, ∀i ii. |y| > 0 n^2 1. For proving that { 1 | n ≧ 0} is not regular, is it possible to use also only the above two conditions? 2. Is it possible to prove that a language is not regular by using only i i. x y z ∈ A, ∀i ii. |xy| ≦ p or i. |y| > 0 ii. |xy| ≦ p --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.116.228 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1421563495.A.D33.html ※ 編輯: irritum (111.250.116.228), 01/18/2015 17:23:59

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