课程名称︰ 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.