3.2 是非判断，对下面的陈述，正确的在陈述后的括号内写T ，否则写F。
(1) 有穷自动机接受的语言是正则语言。（）
(2) 若r1 和r2 是Σ上的正规式，则r1|r 2也是。（）
(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 →S
0|S 21 ，|S1|=2k (k>0 ），|S 2|=2k (k ≥0）。
1
且S 1 是{0,1} 上的串，含有奇数个0 和奇数个 1 。
S2 是{0,1} 上的串，含有偶数个0 和偶数个 1 。
考虑有一个自动机M
接受S1，那么自动机M 1如下：
1
和L(M 1)等价的正规表达式，即S 1 为：
((00|11)|(01|10)(00|11) *(01|10)) *(01|10)(00|11) *
类似的考虑有一个自动机M 2接受S2 ，那么自动机M 2如下：和L(M
)等价的正规表达式，即S 2为：
2
((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
对应的正规表达式： (1(01 * 0)1|0) *
3.6 给出接受下列在字母表 {0,1} 上的语言的 DFA 。
(1) 所有以 00 结束的符号串的集合。
(2) 所有具有 3 个 0 的符号串的集合。
答案
(a) DFA M=({0 ， 1} ， {q 0， q 1 ， q 2}，q 0， {q 2}， δ)
其中 δ定义如下 :
δ（ q 0， 0 ） =q 1 δ（ q 0，1 ） =q 0
δ（ q 1， 0 ） =q 2 δ（ q 1，1 ） =q 0
δ（ q 2， 0 ） =q 2 δ（ q 2，1 ） =q 0
(6)1 *|1 *0(0|10) *(1| ε)
(7) 接受 w 的自动机如下：
(b) 正则表达式 : 1 *01 * 01 *01 *
DFA M=({0 ，1} ， {q 0 ， q 1， q 2， q 3}， q 0 ， {q 3} ，δ)
其中 δ定义如下 :
δ（ q 0， 0 ） =q 1 δ（ q 0，1 ） =q 0
δ（ q 1， 0 ） =q 2 δ（ q 1，1 ） =q 1
δ（ q 2， 0 ） =q 3 δ（ q 2，1 ） =q 2
δ（ q 3， 1 ） =q 3
3.7 构造等价于下列正规表达式的有限自动机。
(1)10| （0|11 ） 0* 1
(2)((0|1) *|(11)) *
答案
(1) DFA M=({0 ， 1} ， {q 0 ，q 1 ， q 2， q 3}， q 0， {q 3}， δ)
其中 δ定义如下 :
