课程名称︰计算理论 Theory of Computing 课程性质︰选修 课程教师︰颜嗣钧 开课学院：电资学院 开课系所︰电机所 考试日期（年月日）︰2017/11/07 考试时限（分钟）：170 试题 : Theory of Computation Fall 2017, Midterm Exam. (Nov. 7, 2017) 1. (20 pts) Let Σ = {0, 1}, answer the following questions (True or False) and prove your answer: (a) the set of nonpalindromes (i.e., Σ* - {w | w = w^R, w ∈ Σ*}) is nonregular; (b) the set of odd-length strings with middle symbol 0 is regular; (c) the set of strings that contain a substring of the form 'wuw' where u ∈ Σ*, w ∈ Σ^+ is nonregular; (d) the set of strings with the property that in every prefix, the number of 0s and the number of 1s differ by at most 2 is regular; (e) if L is nonregular and both of L' and L∩L' are regular, then L∪L' is nonregular. 2. (16 pts) Let A = {xx | x ∈{a, b}*}, and h: {a, b}* → {a, b}* be a homomorphism with h(a) = h(b) = a. (a) What is h(A)? (b) What is h^(-1)(A)? (c) What is h^(-1)(h(A))? (d) What is h(h^(-1)(A))? 3. ( 9 pts) Given Σ = {a, b}, we define Two(x) to be an operation doubling each symbol in x ∈ Σ*. For instance, Two(abab) = aabbaabb, Two(aab) = aaaabb. (a) Define Two(x) recursively. (b) Given a language L, define Two(L) = {x | Two(x), x ∈ L}. Prove that if L is regular, so is Two(L). 4. ( 5 pts) Consider the following operations: prefix(L) = {u | uv ∈ L, ∃v ∈ Σ*}; suffix(L) = {v | uv ∈ L, ∃u ∈ Σ*}; reverse(L)= {x | x^R ∈ L}. Use the closure of regular languages under the reverse and prefix operations to prove that suffix(L) is regular whenever L is regular. 5. ( 5 pts) Use the Myhill-Nerode theorem to show that for any positive integer m, no DFA with less than m states recognizes A_m = {1^k | m divides k} (⊆{1}*). 6. (10 pts) Let L be an infinite regular language. Prove that L can be partitioned into two disjoint infinite regular languages, i.e., L = L_1∪L_2, L_1∩L_2 = Φ, and L_1, L_2 are infinite regular languages. (Hint: Use the pumping lemma.) 7. (10 pts) Consider the following grammar G, where S, A are nonterminals, and a, b are terminals: S → aSA | ε ; A → bA | ε Answer the following questions: (a) Is L(G) regular? Why? (b) Is G ambiguous? Explain your answer. 8. (10 pts) True or False? Score = max{0, Right - ½ Wrong}. No explanations are needed. Here are four regular expressions over the alphabet {a, b}: E_1 = (ab+a*b*b*)* E_2 = ((ab)*(a*b*b*)*)* E_3 = (a+b)* E_4 = a(a+b)* (1) L(E_2) = L(E_3) (2) L(E_3) = L(E_4) (3) L(E_1) = L(E_4) (4) The minimal DFA for L(E_1) has five states. (5) The minimal DFA for L(E_4) has two states. 9. (10 pts) Use the pumping lemma to prove that the following language is not regular: L = {0^m 1^n | m ≦ 2n + 5, m,n ∈ Ν}. 10.( 5 pts) We say that a DFA M for a language A is minimal if there does not exist another DFA M' for A such that M' has strictly fewer states than M. Suppose that M = (Q, Σ, δ, q_0, F) is a minimal DFA for A. Using M, we construct a DFA M_bar for the complement A_bar as M_bar = (Q, Σ, δ, q_0, Q-F). Is M_bar is a minimal DFA for A_bar? Why? --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.4.192 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1510029299.A.73B.html