转换正则表达式到DFA

Question

我一直在试图

转换正则表达式非确定性有限自动机（NFA）首先使用汤普森的建设，并提供：

，看起来正确。

然后我使用子集构造从NFA创建DFA，如下所示。

但这并不看起来是正确的我，例如0，紧接着0根据我所构建的DFA无效。我想知道我应该如何对原始正则表达式中的epsilon进行建模，因为我只是将其视为正常的epsilon。

Answer 1

单个匹配已经完成 - 因此您的图表中的状态B对于一个dfa必须已经是一个接受状态（将它标记为接受不会修复它！）。我不能重建你的想法，但你应该在事情​​结束！

A --0--> (B) 
A --1--> C 
B --0--> (B) 
B --1--> C 
C --0--> (B) 
C --1--> C 

---

如果你开始想通过移除第一部分(0|)从另一个侧面，正则表达式(0|)(0|1)*0可以简化。可以这样做，因为(0|1)匹配(0|)将匹配的所有内容（以及更多）。 你也可以在你的图中看到nfa。

S0->S1->S2->S5 === S7->S7->S8->S11 
S0->S3->S4->S5 === epsilon 

也许这将有助于让你的想法在正确的方向..