将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）。