1.設(shè)有 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}

畫(huà)出狀態(tài)轉(zhuǎn)換矩陣,狀態(tài)轉(zhuǎn)換圖，并說(shuō)明該NFA識(shí)別的是什么樣的語(yǔ)言。

答：由題意可得，狀態(tài)轉(zhuǎn)換矩陣如下：

a

b

0

0,1

0

1

2

2

3

3

狀態(tài)轉(zhuǎn)換圖如下：

識(shí)別語(yǔ)言為：(a | b)*abb

2.NFA 確定化為 DFA

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

1). 上述練習(xí)1的NFA

2). P64頁(yè)練習(xí)3

2.解決空弧：對(duì)初態(tài)和所有新?tīng)顟B(tài)求ε－閉包

1). 發(fā)給大家的圖2

2).P50圖3.6

答：1.(1).

根據(jù)1的NFA構(gòu)造DFA狀態(tài)轉(zhuǎn)換矩陣如下：

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}

根據(jù)1的NFA構(gòu)造DFA狀態(tài)轉(zhuǎn)換圖如下：

識(shí)別語(yǔ)言：b*aa*(ba)*bb， 與1的NFA的識(shí)別的語(yǔ)言相同，都是以abb結(jié)尾的字符串的集合。

1.(2)

狀態(tài)轉(zhuǎn)換矩陣如下：

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}

狀態(tài)轉(zhuǎn)換圖如下：

識(shí)別語(yǔ)言：(00((100) | (0 | 1))(0 | 1)*) | (1((00) | (11*0(0 | 1)*))(0 | 1)*)

2.(1)

狀態(tài)轉(zhuǎn)換矩陣如下：

0

1

2

X

{ABC}

{ABC}

{BC}

{C}

Y

{BC}

{BC}

{C}

Z

{C}

{C}

狀態(tài)轉(zhuǎn)換圖如下：

識(shí)別語(yǔ)言：0*(11*2 | 2)2*

2.(2)

狀態(tài)轉(zhuǎn)換矩陣如下：

a

b

Q

{01247}

{1234678}

{124567}

W

{1234678}

{1234678}

{1245679}

X

{124567}

{1234678}

{124567}

Y

{1245679}

{1234678}

{12456710}

Z

{12456710}

{1234678}

{124567}

狀態(tài)轉(zhuǎn)換圖如下：

識(shí)別語(yǔ)言：(a | bb*a)a*(ba)*bb((bb*aa*(ba)*bb)* | (aa*(ba)*bb)*)

子集法：

f(q,a)={q1,q2,…,qn},狀態(tài)集的子集

將{q1,q2,…,qn}看做一個(gè)狀態(tài)A，去記錄NFA讀入輸入符號(hào)之后可能達(dá)到的所有狀態(tài)的集合。

步驟：

1).根據(jù)NFA構(gòu)造DFA狀態(tài)轉(zhuǎn)換矩陣

①確定DFA的字母表，初態(tài)(NFA的所有初態(tài)集)

②從初態(tài)出發(fā)，經(jīng)字母表到達(dá)的狀態(tài)集看成一個(gè)新?tīng)顟B(tài)

③將新?tīng)顟B(tài)添加到DFA狀態(tài)集

④重復(fù)23步驟，直到?jīng)]有新的DFA狀態(tài)

2).畫(huà)出DFA

3).看NFA和DFA識(shí)別的符號(hào)串是否一致。

總結(jié)

以上是生活随笔為你收集整理的将下图的nfa确定化为dfa_作业8 非确定的自动机NFA确定化为DFA的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。