编译原理期末复习题VIP专享

3.2 是非判断，对下面的陈述，正确的在陈述后的括号内写T，否则写F。 (1)有穷自动机接受的语言是正则语言。（） (2)若r1和r2是Σ上的正规式，则r1|r2也是。（） (3)设 M 是一个 NFA，并且 L(M)＝{x,y,z}，则M 的状态数至少为 4 个。（） (4)令 Σ＝{a,b}，则Σ 上所有以 b 为首的字构成的正规集的正规式为 b*(a|b)*。（） (5)对任何一个 NFA M，都存在一个 DFA M'，使得 L(M')=L(M)。（） (6)对一个右线性文法 G，必存在一个左线性文法 G'，使得 L(G)=L(G')，反之亦然。（） 答案 (1) T (2) T (3) F (4) F (5) T (6) T 3.3 描述下列各正规表达式所表示的语言。 (1) 0(0|1)*0 (2) ((ε|0)1*)* (3) (0|1)*0(0|1)(0|1) (4) 0*10*10*10* (5) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 答案 (1) 以 0 开头并且以 0 结尾的，由 0 和1 组成的符号串。 (2) {α |α ∈{0,1} *} (3) 由 0 和1 组成的符号串，且从右边开始数第 3 位为 0。 (4) 含 3 个 1 的由 0 和1 组成的符号串。 {α |α ∈{0,1} +，且 α 中含有3 个 1 } (5) {α |α ∈{0,1} *,α 中 0 和1 为偶数} 3.4 对于下列语言分别写出它们的正规表达式。 (1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。 (2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 (3) Σ={0,1}上的含偶数个 1 的所有串。 (4) Σ={0,1}上的含奇数个 1 的所有串。 (5) 具有偶数个 0 和奇数个 1 的有0 和1 组成的符号串的全体。 (6) 不包含子串 011 的由 0 和1 组成的符号串的全体。 (7) 由 0 和1 组成的符号串,把它看成二进制数，能被 3 整除的符号串的全体。 答案 (1) 令 Letter 表示除这五个元音外的其它字母。 ((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))* (2) A*B*....Z* (3) (0|10*1)* (4) (0|10*1)*1 (5) [分析] 设S 是符合要求的串，|S|=2k+1 (k≥0）。 则 S→S10|S21，|S1|=2k (k>0），|S2|=2k (k≥0）。 且 S1 是{0,1} 上的串，含有奇数个 0 和奇数个 1。 S2 是{0,1} 上的串，含有偶数个 0 和偶数个 1。 考虑有一个自动机 M1 接受 S1，那么自动机 M1 如下： 和 L(M1)等价的正规表达式，即 S1 为： ((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)* 类似的...