必威体育精装版编译原理期末复习题 .pdfVIP

精品文档

3.2是非判断，对下面的陈述，正确的在陈述后的括号内写T，否则写F。

(1)有穷自动机接受的语言是正则语言。（）

(2)若r和r是Σ上的正规式，则r|r也是。（）

1212

(3)设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。（）

**

(4)令Σ＝{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为b(a|b)。（）

(5)对任何一个NFAM，都存在一个DFAM，使得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)ABZ

**

(3)(0|101)

**

(4)(0|101)1

精品文档

精品文档

(5)[分析]

设S是符合要求的串，|S|=2k+1(k≥0）。

则S→S0|S1，|S|=2k(k0），|S|=2k(k≥0）。

1212

且S是{0,1}上的串，含有奇数个0和奇数个1。

1

S是{0,1}上的串，含有偶数个0和偶数个1。

2

考虑有一个自动机M接受S，那么自动机M如下：

111

和L(M)等价的正规表达式，即S为：

11

***

((00|11)|(01|10)(00|11)(01|10))(01|10)(00|11)

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

222

和L(M)等价