课程名称︰自动机与形式语言 课程性质︰必修 课程教师︰项洁 开课学院：电机资讯学院 开课系所︰资讯工程学系 考试日期（年月日）︰2011/11/22 考试时限（分钟）：180 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : ^n 表示上标，_n 表示下标，￡ 表示属於，Ε 表示包含於 1. Let L Ε {0, 1}* be the language of all the strings that have equal number of 0s and 1s. (a) Give a three-state PDA for L. (b) Give a CFG for L. 2. Show that the class of context-free languages is closed under union, concatenation, and Kleene star. 3. Let A = {0^m 1^n 2^n: m, n ≧ 0} and B = {0^m 1^m 2^n: m, n ≧ 0}. (a) Show that A and B are both context free. (b) Show that the class of context-free languages is not closed under intersection. 4. Let A = {0^p: p is a prime}. (a) Show that A is not regular. (b) Show that A* is regular. 5. We define the quotient of languages L_1 and L_2, denoted as L_1/L_2, to be {w: wx ￡ L_1 for some x ￡ L_2}. Show that the class of regular languages is closed under the quotient operation. 6. Let L Ε {0, 1}* be a regular language, and let A Ε {0, 1}* be a language in which, for each w ￡ A, there exists x ￡ L such that (i) |w| = |x| (ii) w and x differ in at most one symbol position. Show that A is regular. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 59.117.176.59 ※ 编辑: paul112004 来自: 59.117.176.59 (11/22 20:57) ※ 编辑: paul112004 来自: 59.117.176.59 (11/22 20:57)