課程名稱：自動機與形式語言 課程性質︰必修 課程教師︰項潔 開課學院：電機資訊學院 開課系所︰資訊系 考試日期（年月日）︰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