课程名称：自动机与形式语言 课程性质︰必修 课程教师︰项洁 开课学院：电机资讯学院 开课系所︰资讯系 考试日期（年月日）︰2010/11/23 考试时限（分钟）：180分钟 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : 编按： x_i 表下标，x^i 表上标；￡表属於。 Problem 1 (10 points) Find the error in the following proof that all horses are of the same color. CLAIM: In any set of h horses, all horses are of the same color. Proof: By induction on h. Basis: For h=1. In any set containing just one horse, all horses clearly are of the the same color. Induction step: For k≧1 assume that the claim is true for h=k and prove that it is true for h=k+1. Take any set H of k+1 horses. We show that all the horses in H are of the same color. Remove one horse from this set to obtain the the set H_1 with just k horses. By the induction hypothesis, all the horses in H_1 are of the same color. Now replace the removed horse and remove a different one to obtain the set H_2. By the same argument, all the horses in H_2 are of the same color. Therefore all the horses in H must be of the same color, and the proof is complete. Problem 2 (20 points) a. Show that, if M is a DFA that recognizes language B, swapping the accept and and non-accept states in M yields a new DFA that recognizes the complement of B. Conclude that the class of regular languages is closed under comple- ment. b. Show by giving an example that, if M is an NFA that recognizes language C, swapping the accept and non-accept states in M does not necessarily yield a new NFA that recognizes the complement of C. Can you conclude from this example that the class of languages recognized by NFAs is NOT closed under complement? Explain your answer. Problem 3 (15 points) For any string w = w_1w_2 ... w_n, the reverse of w, written w^R, is w in reverse order, w_n ... w_2w_1. For any language A, let A^R = {w^R | w ￡ A}. Show that if A is regular, so is A^R. Problem 4 (20 points) a. Let C be a context-free language and R be a regular language. Prove that the language C∩R is context free. b. Use part (a) to show that the language A = {w| w ￡ {a,b,c}* and contains equal numbers of a's, b's, and c's} is not a CFL. Problem 5 (15 points) Prove the language L = {the set of strings of the form 0^i1^j such that the greatest common divisor of i and j is 1} is not regular. Problem 6 (15 points) Show that, if G is a CFG in Chomsky normal form, then for any string w ￡ L(G) of length n≧1, exactly 2n-1 steps are required for any derivation of w. Problem 7 (15 points) A context-free grammar G = (V,Σ,R,S) is regular if and only if R 包含於 (V-Σ) ×Σ*((V-Σ)∪{ε}). Show that a language is regular if and only if it is generated by a regular grammar. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.4.191