编译原理期末复习题

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) 0101010

*

*

*

*

*

*

**

(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)*

类似的考虑有一个自动机M2接受S2，那么自动机M2如下：

和L(M2)等价的正规表达式，即S2为： ((00|11)|(01|10)(00|11)*(01|10))* 因此，S为：

((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0| ((00|11)|(01|10)(00|11)*(01|10))*1

(6)1*|1*0(0|10)*(1|ε)

(7)接受w的自动机如下：

对应的正规表达式：(1(01*0)1|0)*

3.6 给出接受下列在字母表{0,1}上的语言的DFA。 (1) 所有以00结束的符号串的集合。 (2) 所有具有3个0的符号串的集合。

答案

(a) DFA M=({0，1}，{q0，q1，q2}，q0，{q2}，δ) 其中δ定义如下:

δ（q0，0）=q1 δ（q0，1）=q0 δ（q1，0）=q2 δ（q1，1）=q0 δ（q2，0）=q2 δ（q2，1）=q

(b)正则表达式: 1*01*01*01*

DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，δ) 其中δ定义如下:

δ（q0，0）=q1 δ（q0，1）=q0 δ（q1，0）=q2 δ（q1，1）=q1 δ（q2，0）=q3 δ（q2，1）=q2 δ（q3，1）=q3

3.7构造等价于下列正规表达式的有限自动机。 (1)10|（0|11）01 (2)((0|1)|(11))

*

* *

答案

(1) DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，δ)

其中δ定义如下:

(2) δ（q0，0）=q1 δ（q0，1）=q2 (3) δ（q1，0）=q1 δ（q1，1）=q3 (4) δ（q2，0）=q3 δ（q2，1）=q1

(5)

(6) (2) DFA M=({0，1}，{q0}，q0，{q0}，δ) (7) 其中δ定义如下:

(8) δ（q0，0）=q0 δ（q0，1）=q0

(9)

3.8 给定右线性文法G： S->0S|1S|1A|0B A->1C|1 B->0C|0 C->0C|1C|0|1

试求一个于G等价的左线性文法G'

3.9 试对于下列正规表达式使用证明定理3。5的构造算法构造非确定的有限自动机。请给出每个自动机在处理输入符号串ababbab的过程中的动作序列。 (1) (a|b)

*

*

(2) (a|b)

**

**

(3) ((ε|a)b)

3.10 转换练习3.9中的每个 NFA 为 DFA 。并给出每个DFA在处理输入符号串ababbab的过程中的动作序列。

3.11 试把练习3.10中得到的DFA的状态给以最小化。

答案

(1),(2),(3)的DFA M相同，化简结果为：

(4)

3.12 我们可以证明两个正规表达式是等价的，如果它们的最小状态DFA是相同的（除了状态的名字以外）。利用这一结论，请说明下列正规表达式都是等价的。 (1) (a|b)

*

*

(2) (a|b)

**

**

(3) ((ε|a)b)

答案

根据3.11的结果知这几个正规表达式是等价的。

3.13 对于下列正规表达式构造最小状态的DFA。 (1) (a|b)a(a|b) (2) (a)b)a(a|b)(a|b) 5． 对如下文法：

G[S] ： S a b S | a a B | a d

B b b B | b

分别给出句子abaabbb和ad的句柄 句子ad的语法分析树为：

**