automata - 将 NFA 转换为 DFA

Question

我无法理解如何转换。

如果 2 得到一个 'a' 的输入，它会因为空字符串而变成 (1,4) 还是 (1,2,4)？

谢谢！

Answer 1

如果 stateQ2得到 'a' 的输入，则下一个 states 可能是Q1, Q2, 0r Q4。

在您的 NFA 中，您获得最终状态Q4

其等效 DFA 如下：

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

WhereQ1和Q2是最终状态。

它的正则表达式是： a (a + ba)* (b + ε )

ε空符号在哪里（epsilon）

Answer 2

我们开始通过识别空输入闭包集将 NFA 转换为 DFA（从这里开始，我将用 L-闭包表示空输入闭包）。
L(1)=(1,2) 我们可以在空输入上从 1 访问 2。
L(2)=(2) 没有从 2 出来的空输入边
L(3)=(3) 没有从 3 出来的空输入边
L(4)=(1,2,4) 我们可以从 4 访问 1 和从 1 访问 2。

如果 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  

由于 NFA 中 4 是接受节点，因此在 DFA 中包括 4 的节点将是接受节点，即 (1,2,3,4) 和 (1,2,4)。