課程名稱︰自動機與形式語言 課程性質︰大三上必修 課程教師︰陳偉松 (Tony Tan) 開課學院：電資 開課系所︰資訊工程學系 考試日期（年月日）︰106/1/10 考試時限（分鐘）：180 試題 : In the following all the languages are over the alphabet Σ = {0, 1}. (1) Consider the following automaton A. http://i.imgur.com/qfvay5X.png (i) [2 points] Is A deterministic or non-deterministic? (ii) [2 points] Is 1010001 accepted by A? Is 0001110 accepted by A? (iii) [2 points] Is there a word of length 7 that is accepted by A? If there is, give one. (iv) [2 points] What is the regular expression for L(A)? Hint: Consider its complement. (2) Consider the following CFG G with the following rules, where S is the starting variable: S → 0S1 | 1S0 | ɛ (i) [2 points] Is 10110 generated by G? Is 1010 generated by G? (ii) [2 points] Is there a word of length 8 that is generated by G? If there is, give one. (iii) [2 points] Is there a word of length 13 that is generated by G? If there is, give one. (iv) [2 points] Prove that the language L(G) is not regular. (3) [4 points] Consider the following language: L := { M | M is a Turing machine that accepts the string 101 } └ ┘ Prove that L is undecidable. (4) [5 points] Recall the definition of the problem SAT. ┌───────────────────────┐ │ SAT │ ├───────────────────────┤ │ Input: A propositional formula φ in CNF. │ │ Task: Output True, if φ is satisfiable. │ │ Otherwise, output False. │ └───────────────────────┘ We know that SAT is NP-complete. Recall also the 3-color problem.﹡ ┌───────────────────────┐ │ 3-color │ ├───────────────────────┤ │ Input: A (undirected) graph G = (V, E). │ │ Task: Output True, if G is 3-colorable. │ │ Otherwise, output False. │ └───────────────────────┘ We have proved that 3-color is NP-complete by reducing SAT to 3-color. Is there a polynomial-time reduction from 3-color to SAT? If there is, give one such reduction. ────────────────── ﹡ A graph G is 3-colorable, say by R, G, B (Red, Green, Blue), if we can color the vertices with R, G, B such that for every edge (u, v) in G, the vertices u and v have different colors. Here one vertex must have exactly one color. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.114.180.11 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1484278904.A.540.html ※ 編輯: kevin1ptt (58.114.180.11), 01/13/2017 11:44:09