编译原理期末复习题.docx

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)对任何一个NFAM，都存在一个DFAM'，使得L(M')=L(M)。（）
(6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（）

答案(1)T(2)T(3)F(4)F(5)T(6)T3.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)*
类似的考虑有一个自动机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)DFAM=({0，1}，{q0，q1，q2}，q0，{q2}，δ)
其中δ定义如下:
δ（q0，0）=q1δ（q0，1）=q0
δ（q1，0）=q2δ（q1，1）=q0
δ（q2，0）=q2δ（q2，1）=q0

(b)正则表达式:1*01*01*01*
DFAM=({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）0*1
(2)((0|1)*|(11))*

答案
DFAM=({0，1}，{q0，q1，q2，q3}，q0，{q3}，δ)其中δ定义如下:
δ（q0，0）=q1δ（q0，1）=q2
δ（q1，0）=q1δ（q1，1）=q3
δ（q2，0）=q3δ（q2，1）=q1

(2)DFAM=({0，1}，{q0}，q0，{q0}，δ)
其中δ定义如下:
δ（q0，0）=q0δ（q0，1）=q0

3.8给定右线性文法G：
S->0S|1S|1A|0B
A->1C|1
B->0C|0
C->0C|1C|0|1
试求一个于