精品文档
+B +C D E +F C C E F F D E A E
第3题： 确定化： . I0 I1 A –S VQ QU B VQ VZ QU C QU V QUZ D +VZ Z Z E V Z . F +QUZ VZ QUZ G +Z Z Z
重新命名，以A、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ代替{S},{VQ },{QU },{ VZ },{ V },{QUZ},{Z}得DFA 其中A为初态，D，F，G为终态 . 0 1 –A B C B D C C E F +D G G E G . +F D F +G G G
第4题： (1)确定化： Ia Ib A –+0 01 1 B +01 01 1 C 1 0
重新命名，以Ａ、Ｂ、Ｃ代替{0}、{01}、{1}得ＤＦＡ 其中A为初态，A，B为终态
–+A +B C a B B A b C C 精品文档
精品文档
最小化：
初始分划得终态组{A,B}，非终态组{C} Π0：{A,B}，{C}
对终态组进行审查，判断A和B是等价的，故这是最后的划分 重新命名，以A、C代替{A,B}、{C}得DFA –+A C a A A b C
(2)这是DFA，直接最小化
初始分划得：终态组{0}，非终态组{1,2,3,4,5} Π0：{0}，{1,2,3,4,5}
对{1,2,3,4,5}进行审查：
∵{4} 输入a后到达{0}，{1,2,3,5}输入a后到达{1,3,5}，故得到新分划 {0,1,3,5}，{4} Π1：{0}，{4}，{1,2,3,5} 对{1,2,3,5}进行审查：
∵{1,5} 输入b后到达{4}，{2,3} 输入b后到达{2,3}，故得到新分划 {1, 5}，{2,3} Π2：{0}，{4}，{1, 5}，{2,3}
对{1, 5}，{2,3}进行审查： {1, 5} 输入a后到达{1, 5}
{2} 输入a后到达{1}，{3} 输入a后到达{3}，故得到新分划{2}，{3} Π3：{0}，{2}，{3}，{4}，{1, 5} 这是最后分划了
重新命名，以0，2，3，4，1代替{0}，{2}，{3}，{4}，{1, 5}得DFA略 第7题
a a 首先判断E，F为多余状态
根据正则文法转化为NFA的方法构造NFA b a A S
B b a b b Q b b D b
a Z
确定化：
精品文档
精品文档
Ia Ib a b 0 –S A Q –0 1 2 1 A A BZ 1 1 3 2 --? Q Q DZ 2 2 4 3 +BZ Q D +3 2 5 4 +DZ A B +4 1 6 5 D A B 5 1 6 6 B Q D 6 2 5
最小化：
初始分划得：终态组｛3,4｝，非终态组｛0,1,2,5,6｝ Π0：｛3,4｝,｛0,1,2,5,6｝
对｛0,1,2,5,6｝进行审查： {1,2}输入b到达｛3,4｝，而{0,5,6}输入b到达｛2,5,6｝，故得到新分划｛1,2｝,｛0,5,6｝ Π1：｛3,4｝,｛1,2｝,｛0,5,6｝ 对｛0,5,6｝进行审查：
{0}经过b到达｛２｝，{5,6}经过b到达｛5,6｝，故得到新分划｛0｝｛5,6｝ Π3：{0}，{1,2}，{3,4}，{5,6} 这是最后划分了。
重新命名，以0，1，3，5代替{0}，{1,2}，{3,4}，{5,6}得DFA略
第9题
这是DFA，直接最小化 初始分划得：终态组｛6,7｝，非终态组｛1,2,3,4,5｝ Π0：｛6,7｝,｛1,2,3,4,5｝
对｛1,2,3,4,5｝进行审查： {1,2}输入b到达｛2｝，而{3,4}输入b到达｛6,7｝，{5}输入b不会有任何动作，故得到新分划｛1,2｝,｛3,4｝,{5} Π1：｛6,7｝,｛3,4｝,｛5｝,｛1,2｝
这是最后划分了。
重新命名，以1，3，5，6代替｛1,2｝,｛3,4｝,｛5｝,｛6,7｝得DFA
c b b a b 6 1 3 d a
5
所识别的语言是b*a (c| da)*bb*
精品文档
精品文档
第11题
根据正则文法（左线性文法）转化为NFA的方法构造NFA：
a a
Z A a ε b
S
确定化： Ia Ib 0 1 --?
–+ZS A A –+0 2 A 重新命AS 1 名，以+AS AS A +2 0、1、2
代替{ZS}、{A}、{AS}得DFA 其中0为初态，0，2为终态 a
a,b a
0 2 1
b
所识别的语言是：ε| (a|b) a (ba|a)*
第13题
（1） 假设d {A,B,…,Y,Z} n {0,1,2,…,8,9}，文法可以等价得化为：
<单词>—> <标识符> | <整数>
<标识符>—> <标识符>d | <标识符>n | d <整数>—><整数>n | n
（2） 根据正则文法（左线性文法）转化为NFA的方法构造NFA：
重新命名状态，令A、B、C分别代表<单词>、<标识符>、<整数>
d,n d ε
A S B
n C n 精品文档
ε a 1 2 2 b 1 1