automation - 谁能告诉我给定语言的正则表达式？

Question

所有包含偶数个 0 或偶数个 1 的字符串。在这里，我问的是“或”而不是“和”。

我想出了这个：(1*01*0)*|(0*10*1)*到目前为止...但这对我来说似乎是错误的，因为当您为上述语言绘制 DFA 时，您甚至可以接受 111 或000 也是。

标签： automationcompiler-constructionautomata

Answer 1

对于零，允许任意数量的零部分与任意数量的前导非零和分隔非零。然后允许任何尾随非零。如果字符串与此模式不匹配，则它有奇数个零。

(1*01*0)*1*

并且要为 0 或 1 执行此操作，只需使用1s 进行复制并将其添加为整个事物的替代方案。

(1*01*0)*1*|(0*10*1)*0*

而且，111并且000都正确满足条件，因为111有偶数个0s 并且000有偶数个1s。不应该工作的例子是1101or 011100。