不以 01 结尾的字符串的自动机正则表达式

Question

不以 01 结尾的字符串的自动机

我无法获得生成不以 01 结尾的字符串的 alphabet={0,1} 的自动机的正则表达式。

这是状态图：

状态图

我用 Matthew McClintock 的 Visual Automata Simulator 工具得到了这个状态图，所以我测试了一些字符串，比如空字符串 e、"0"、"1"、"00"、"10"、"11" 和那些做不是以 01 结尾，它似乎有效。

你能帮我获取正则表达式吗？。我没有正式介绍计算机自动机理论，所以我几乎不了解 dfa，nfa 的概念，命名法对我来说有点奇怪。

我试图获得正则表达式，一个是：

(0+1)*(00+10+11)

但我不确定这是否正确。

然后根据图表我尝试了这样的事情：

1*(00*1+0+0*1)*+1(00*1+0*1)*

或类似的事情。你知道我可以测试正则表达式吗？

Answer 1

正如我在评论中所说，您的第一次尝试非常接近。这应该有效：

(0+1)*(00+10+11)+0+1+ε

或者，用程序员的话说，

^([01]*(00|10|11)|0|1|)$

编辑：谢谢nhahtdh，我确实有。

Answer 2

你至少应该想出这个 DFA：

然后使用here描述的步骤来解决正则表达式。

R1 = 1R1 + 0R2 +       λ
R2 =       0R2 + 1R3 + λ
R3 = 1R1 + 0R2

剩下的留给你作为练习。

Answer 3

这里是不以'01'结尾的FA，Regular Language是((0+1)*(00+11+10))