推 andy74139 :已收錄至精華區!! 11/23 21:37
課程名稱：自動機與形式語言
課程性質︰必修
課程教師︰項潔
開課學院：電機資訊學院
開課系所︰資訊系
考試日期（年月日）︰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