第3章 习题解答
1.构造正规式1(0|1)*101相应的DFA. [答案]
先构造NFA
确定化 X A AB AC ABY X A B C D 转化成DFA：
==============================================================
2.将下图确定化：
0 A AC A AC 0 A C A C 1 A AB AB ABY AB 1 A B B D B 重新命名，令AB为B、AC为C、ABY为D [答案]
S VQ QU VZ V QUZ Z S A B C D E F 0 VQ VZ V Z Z VZ Z 0 A C D F F C F 1 QU QU QUZ Z QUZ Z 1 B B E F E F 重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。
转化为DFA：
================================================================ 3.把下图最小化：
[答案]
（1）初始分划得Π0：终态组{0}，非终态组{1,2,3,4,5}
对非终态组进行审查：
{1,2,3,4,5}a {0,1,3,5}
而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5} ∵{4} a {0}，所以得新分划 （2）Π1：{0}，{4}，{1,2,3,5} 对{1,2,3,5}进行审查： ∵{1,5} b {4}
{2,3} b {1,2,3,5}，故得新分划 （3）Π2：{0}，{4}，{1, 5}，{2,3} {1, 5} a {1, 5}
{2,3} a {1,3}，故状态2和状态3不等价，得新分划 （3）Π3：{0}，{2}，{3}，{4}，{1, 5} 这是最后分划了 （4）最小DFA：
======================================= 4.构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式和正规文法。 [答案]
按题意相应的正规表达式是0*(100*)*0* 构造相应的DFA，首先构造NFA为
0 0 5 0 ε X 1 ε 1 2 3 0 4 ε ε 6 ε 7 ε Y ε 用子集法确定化
I {X,1,2} S {1, 2} A {3} B {4,5,6,2,7,Y} C {5,6,2,7,Y} D DFA： I0 {1, 2} A {1, 2} A {4,5,6,2,7,Y} C {5,6,2,7,Y} D {5,6,2,7,Y} D I1 {3} B {3} B / {3} B {3} B
0 0 1 A S 1 B 1 0 1 C 0 D 0
可最小化，终态组为G1={C, D}，非终态组为G2={S, A, B} 对于G2分析：f(S,0)=A, f(A,0)=A, 后继状态均属于G2 而f(B,0)=C, 后继状态属于G1 将G2分割成G21={S，A}， G22={B}
经检查DFA最小状态集有三个，可用S、B、D表示。 或：
按题意相应的正规表达式是0*(0 | 10)*0* 首先构造NFA为
用子集法确定化 I {X,0,1,3,Y} {0,1,3,Y} {2} {1,3,Y} DFA：
I0 {0,1,3,Y} {0,1,3,Y} {1,3,Y} {1,3,Y} I1 {2} {2} / {2} S 1 2 3 4 0 1 2 3 2 3 4 4 3
可最小化，终态组为{1,2,4}，非终态组为{3}，{1,2,4}0 所以1,2,4为等价状态，可合并。
{1,2,4}，{1,2,4}1 {3}，
=============================================
5．给出下列文法所对应的正规式：
S->0A|1B A->1S|1 B->0S|0 [答案]
解方程组S的解： S=0A|1B
A=1S|1 B=0S|0
将A、B产生式的右部代入S中
S=01S|01|10S|10=（01|10）S|（01|10） 所以：S= (01|10)*(01|10)
================================================= 6.为下边所描述的串写正规式，字母表是 {a,b}.
a) 以ab 结尾的所有串
b) 包含偶数个b但不含a的所有串
c) 包含偶数个b且含任意数目a的所有串 d) 只包含一个a的所有串 e) 包含ab子串的所有串 f) 不包含ab子串的所有串 [答案]
注意 正规式不唯一
a) (a|b)*ab b) (bb)*
c) (a*ba*ba*)* d) b*ab*
e) (a|b)*ab(a|b)* f) b*a*
======================================
7.请描述下面正规式定义的串. 字母表S = {0，1}.
a) 0*(10+)*0*
b) (0|1)*(00|11) (0|1)* c) 1(0|1)*0 [答案]
a) 每个1至少有一个0跟在后边的串
b) 所有含两个相继的0或两个相继的1的串 c) 必须以 1 开头和0结尾的串
========================================== 8. 构造有穷自动机.
a) 构造一个DFA，接受字母表S = {0, 1}上的以01 结尾的所有串
b) 构造一个DFA，接受字母表S = {0, 1}上的不包含01 子串的所有串. c) 构造一个NFA，接受字母表S = {x,y}上的正规式x(x|y)*x描述的集合
d) 构造一个NFA，接受字母表S = {a, b}上的正规式(ab|a)*b+描述的集合并将其转换为等价的DFA.以及最小状态DFA [答案]