课后答案网 http://www.khdaw.com
φ 给状态编号：
0 1 2 3 a 1 1 0 3 b 2 2 3 3 φ φ
a
a 0 1
a b b b
b 2 3
a
最小化：
{0,1},{2,3}{0,1}?{1} {0,1}?{2}ab{2,3}?{0,3} {2,3}?{3}
ab{0,1},{2},{3}
a a
b b 1 2 0 a b (b)
b b a 2 3 0
a b a a b b a 4 5 1 a a
已经确定化了,进行最小化
课后答案网 http://www.khdaw.com
课后答案网 http://www.khdaw.com
最小化：
{{0,1}, {2,3,4,5}}{0,1}a?{1} {0,1}b?{2,4}{2,3,4,5}a?{1,3,0,5} {2,3,4,5}b?{2,3,4,5}{2,4}a?{1,0} {2,4}b?{3,5}{3,5}a?{3,5} {3,5}b?{2,4}{{0,1},{2,4},{3,5}}{0,1}a?{1} {0,1}b?{2,4}{2,4}a?{1,0} {2,4}b?{3,5}{3,5}a?{3,5} {3,5}b?{2,4}
b b a 1 2 0
a b
a
P64–14
(1) 0 1 0 0 (2):
X (010|)* 1 Y
2
0 1 ? ? 1 X
0
确定化： {X,1,Y} 0 {1,Y} Y 1 {2} 课后答案网 http://www.khdaw.com
课后答案网 http://www.khdaw.com
{1,Y} {2} φ 给状态编号： 0 1 2 3 0 1 1 1 3 1 2 2 3 3 {1,Y} {1,Y} φ {2} φ φ 0
0 1 0 1 0 1 1 1 2 3
0 最小化：
{0,1},{2,3}{0,1}0?{1} {0,1}1?{2}{2,3}0?{1,3} {2,3}1?{3}{0,1},{2},{3}
0 1 1 1 1 3 0 0 0 第四章
P81–1
(1) 按照T,S的顺序消除左递归
G?(S)S?a|^|(T) ?T?STT??,ST?|?递归子程序： procedure S; begin
if sym='a' or sym='^' then abvance else if sym='('
课后答案网 http://www.khdaw.com
课后答案网 http://www.khdaw.com
then begin advance;T;
if sym=')' then advance; else error; end else error end;
procedure T; begin S;T? end;
procedure T?; begin
if sym=',' then begin advance; S;T? end end; 其中:
sym:是输入串指针IP所指的符号 advance:是把IP调至下一个输入符号 error:是出错诊察程序 (2)
FIRST(S)={a,^,(} FIRST(T)={a,^,(} FIRST(T?)={,,?} FOLLOW(S)={),,,#} FOLLOW(T)={)} FOLLOW(T?)={)} 预测分析表
S T a ^ ( ) , # S?(T) T?ST? T?ST? T?ST? S?a S?^ T? 是LL(1)文法
T??? T??,ST? P81–2
文法：
课后答案网 http://www.khdaw.com