regex - 描述 {0,1} 语言且没有交替 0 的正则表达式

Question

它主要在标题中，我的意思是交替出现两次 0 之间只有一个 1 或 0。所以没有这样的 010 或 000 出现。

我试图理解这个问题的理论性质，所以我更喜欢仅使用串联、联合和闭包(10、1|0 和 10*)的答案。

请注意，这不是一个家庭作业问题，我只是对这个问题感兴趣，所以请不要对此影响发表光顾评论。

编辑:将第一段中的措辞从“出现之间”更改为“两次出现之间”。

Answer 1

第一个重要的观察是我们可以减少问题:如果 S 是允许的并且是 1或以两个 1 结尾， S 与任何允许的序列连接仍然允许。那么什么是有效的 S 呢？

1明确在 S 中，以及任何多于一个的序列 ​​1总是以 11 结尾在 S 也是如此。

一个 01后面只能跟另一个 1 ，作为 0会给 010 .这以 11 结束，因此是有效的 S。

一个 00后面只能跟 11 , 如 0000 , 0001和 0010都有交替的零。这以 11 结束，因此是有效的 S。

所以这告诉我们任何 S 匹配 ^(1|011|0011)*$ .但我们还没有完成，因为还有一些其他序列对 S 无效但它们本身是允许的序列，因此可以连接到 S。

0

00

01

001

000当然，这是不允许的，并且任何更长的东西要么在 S 中，要么本身是不允许的。

所以整个正则表达式匹配允许的序列是:

^(1|011|0011)*(|0|00|01|001)$

那是零个或多个 S 序列，可选地后跟我们允许的非 S 序列之一。