課程名稱︰ Formal Languages and Automata Theory
課程性質︰ 必 修
課程教師︰ 項 潔
開課學院： 資訊電機學院
開課系所︰ 資訊系
考試日期（年月日）︰ 2 Dec, 2014
考試時限（分鐘）：
試題 :
(Closed book exam)
1 (10 points) Let R = {(a,a), (b,a), (b,c), (c,a), (c,d), (d,b)} be a relation defined on A = {a,b,c,d}. Find the reflexive transitive closure of R.
2 (15 points) Show that the cardinality of the power set of N is bigger than that of N.
3 (15 points) Show that if L is regular, then the language {x^R | x 屬於 L} is regular.
4 (20 points)
(a) Let A = {1^ky|y屬於{0,1}* and y contains at least k 1s, for some k >=1}. Show that A is regular.
(b) Let B = {1^ky|y屬於{0,1}* and y contains at most k 1s, for some k>=1 }. Show that B is not regular.
5 (20 points) Give context free grammars that generate the following languages. In all parts the alphabet sigma is {0,1}
(a) {w| w starts and ends with the same symbol}
(b) {w|w contains more 1s than 0s}
6 (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 w contains an equal number of as, bs, and cs} is not context free.