编译原理第3章文法和语言 下载本文

0 ε ε ε ε

将T0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名,分别用0、

1、2、3、4、5、6、7、8、9、10、11、12、13、14表示。因为2、7、8、10、12中含有Y,

所以它们都为终态。 0 1 0 1 1 2 3 2 3 4 5 4 6 5 2 3 6 7 3 7 8 9 8 10 11 9 12 9 10 10 3 11 13 5

12 6 13 14 14 7 3 0 1 0 12 1 2 7 10 8 3 4 5 6 9

11 13 14 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1

(3)先构造NFA: 先构造NFA:

用子集法将NFA确定化 ε a b X X T0=X A A

ABCD T1=ABCD BE BY BE

ABCDE BY

ABCDY T2=ABCDE BEF BEY BEF

ABCDEF BEY

ABCDEY T3=ABCDY BE BY

T4=ABCDEF BEF BEY

T5=ABCDEY BEF BEY

将T0、T1、T2、T3、T4、T5重新命名,分别用0、1、2、3、4、5表示。因为3、5中含有Y,

所以它们都为终态。 a b 0 1 1

2 3 2 4 5 3 2 3 4 4 5 5 4 5 X a A εB a,b ε

D a E a F C ε Y ε ε b ε b

0 a 1 b 3 2 a 5 a 4 b a b a b a b

(4)先构造NFA:

用子集法将NFA确定化: ε a b X X T0=X A A

ABDEF T1=ABDEF CI G CI CI G G T2=CI DY DY

ABDEFY T3=G H H

ABEFH

T4=ABDEFY CI G

T5=ABEFH CI G

将T0、T1、T2、T3、T4、T5重新命名,分别用0、1、2、3、4、5表示。因为4中含有Y,

所以它为终态。 a b 0 1 1 2 3 2