编译原理：非确定的自动机NFA确定化为DFA

2024-04-12 10:11:56

1.设有 NFA M=( {0,1,2,3}, {a,b},f,0,{3} )，其中 f(0,a)={0,1} f(0,b)={0} f(1,b)={2} f(2,b)={3}

画出状态转换矩阵,状态转换图，并说明该NFA识别的是什么样的语言。

解析：

a

b

0

{0,1}

0

1

2

2

3

3

状态转换图如下：
　　　　　　　　　　　　　　　　　　　　　　

识别语言为：(a | b)*abb

2.NFA 确定化为 DFA

1.解决多值映射：子集法

1）. 上述练习1的NFA

解析：

根据1的NFA构造DFA状态转换矩阵如下：

a

b

A

{0}

{0,1}

{0}

B

{0,1}

{0,1}

{0,2}

C

{0,2}

{0,1}

{0,3}

D

{0,3}

{0,1}

{0}

　　根据1的NFA构造DFA状态转换图如下：

　　

　　识别语言：b*aa*(ba)*bb，与1的NFA的识别的语言相同，都是以abb结尾的字符串的集合。

2）. P64页练习3

状态转换矩阵如下：

0

1

A

{S}

{Q,V}

{Q,U}

B

{Q,V}

{V,Z}

{Q,U}

C

{V,Z}

{Z}

{Z}

D

{Q,U}

{V}

{Q,U,Z}

E

{V}

{Z}

F

{Q,U,Z}

{V,Z}

{Q,U,Z}

G

{Z}

{Z}

{Z}

状态转换图如下：

　　　　　　　　　　　　　　　　　　　　　　　　　　