課程名稱︰自動機與形式語言
課程性質︰系必修
課程教師︰項潔
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2012/11/06
考試時限（分鐘）：120min
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Problem 1.(10points)
Let A be the set of all infinite sequences over {0,1}.
Show that A is uncountable.
Problem 2.(15points)
Prove that L={0^m1^n: m,n≧0 are integers with m≠n} is not regular.
Problem 3.(20points)
A grammar G = (V,Σ,R,S) is regular if all rules in R are of the form:
A→aB,A→a,or A→ε,when A,B 屬於 V and a 屬於Σ
Show that a language L is regular if and only if there is a regular grammar G
such that L(G)=L.
Problem 4.(20points)
Is the class of context-free language closed under ∪,。,*,∩,-(complement)?
Justify your answer:[Hint:Do in that order.]
Problem 5.(20points)
Answer following question:
(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,b and c} is not
context-free.
Problem 6.(15points)
Let D ={xy|x,y 屬於 {0,1}* and |x|=|y| but x≠y}. Show that D is context-free.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.139
※ 編輯: a123zyx 來自: 140.112.30.139 (11/06 14:59)
※ 編輯: a123zyx 來自: 140.112.30.139 (11/06 14:59)