課程名稱︰自動機與形式語言 課程性質︰資工系大三必修 課程教師︰項潔 開課學院：電機資訊學院 開課系所︰資訊工程學系 考試日期（年月日）︰2016/01/12 考試時限（分鐘）：170 試題 : Problem 1 (20 points) For each of the classes of languages Regular, Context-Free, Decidable, and Turing-Recognizable, state whether they are closed under union, concatenation, Kleene star, intersection, and complement. For each negative answer, explain why. Problem 2 (15 points) Let A = {〈R, S〉| R and S are regular expressions and L(R) ⊆ L(S)}. Show that A is decidable. Problem 3 (15 points) If A ≦ B and B is a regular language, does that imply that A is a regular m language? Why or why not? Problem 4 (15 points) _ Give an example of an undecidable language B, where B ≦ B. m Problem 5 (15 points) Prove that there exists an undecidable subset of {1}*. Problem 6 (15 points) A grammar G = {V, Σ, R, S} is regular if every rule in R is of the form A → aB or A → ε Show that a language L is regular iff it can be generated by a regular grammar. Problem 7 (15 points) Show that a language L is decidable iff there is an enumerator E that enumerates the members of L in non-decreasing order. (That is, if E prints out u , u , u , 1 2 3 u , ..., then |u | ≦ |u | if i ≦ j.) 4 i j --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.212.7 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1452579595.A.580.html ※ 編輯: xavier13540 (140.112.212.7), 01/12/2016 14:20:39