regex - 正则表达式 0*1*1+11*0*1 DFA

Question

下面的自动机会接受表达式“0*1*1+11*0*1”吗？

由于表达式生成以“1”结尾的字符串，我相信自动机会接受它。

但是，我在其中一篇引用文献中发现答案并非如此。有人可以解释一下吗？

注意:+表示或操作。

Answer 1

没有。您的 DFA 等效于表达式 (0*1+)+

您指定的表达式需要至少三个 1 才能被接受。将其分解成多个部分

0*
1*
1+ <-- Required at least once
1  <-- Required
1*
0*
1 <-- Required

与您的表达式等效的 DFA 需要表示如下所示:

使用 Regex visualizer 创建的图像，它允许您从正则表达式生成这些图表。

更新:如果 + 表示或，这会改变一些事情。您原来的 DFA 仍然不等效。您错过了如果接受的字符串以 1 开头，则需要至少再跟一个 1 才能被接受。表达式的 DFA 如下所示:

通过在可视化工具中输入 0*1*1|11*0*1 生成。