將NFA轉換爲DFA

Question

NFA http://i48.tinypic.com/2lwof1z.png

我無法理解如何轉換。

如果2得到'a'的輸入，它會因爲空串而變成（1,4）或（1,2,4）嗎？

謝謝！

Answer 1

如果狀態Q2獲得'a'的輸入，則下一狀態可以是Q1，Q2,0rQ4。

在你NFA你得到的最終狀態Q4

它等價的DFA是如下：

    a- 
       || 
       ▼| 
--►(Q0)---a---►((Q1))---b----►((Qf)) 
       ▲-----a--------| 

凡Q1和Q2是最終狀態。

而且其正則表達式爲：a(a + ba)*(b + ε)

哪裏ε是空符號（ε）

Answer 2

我們開始通過識別空輸入閉集集合（從這裏開始，我將通過L閉包來表示空輸入閉包）來將NFA轉換爲DFA。
L（1）=（1,2）我們可以在空輸入中從1開始訪問2。
L（2）=（2）沒有從2輸出空輸入邊緣。
L（3）=（3）沒有空的輸入邊緣從3.
L（4）=（1， 2,4），我們可以從圖4和2從1

訪問1如果2得到由於 （的 'A'，將成爲輸入1,4）或（1,2,4）空字符串？

如果2得到'a'的輸入，它將變成L（1）UL（4）=（1,2,4）。由於我們的起始節點在NFA中是1，所以在DFA中它將是L（1），它是（1,2）。

T((1,2),a)=L(1)UL(3)UL(4)=(1,2,3,4) 
T((1,2),b)=F 
T((1,2,3,4),a)=L(1)UL(3)UL(4)=(1,2,3,4) 
T((1,2,3,4),b)=L(4)=(1,2,4) 
T((1,2,4),a)=L(1)UL(3)UL(4)=(1,2,3,4) 
T((1,2,4),b)=F 

由於圖4是在一個NFA接受節點，在DFA的節點包括4將被接受的節點，它們是（1,2,3,4）和（1,2,4）。