课程名称︰自动机与形式语言 课程性质︰资工系大三必修 课程教师︰项洁 开课学院：电机资讯学院 开课系所︰资讯工程学系 考试日期（年月日）︰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/cn.aspx?n=bbs/NTU-Exam/M.1452579595.A.580.html ※ 编辑: xavier13540 (140.112.212.7), 01/12/2016 14:20:39