接受字符串的正则表达式，其中每两个零后跟一个

Question

所以我正在寻找一种方法来编写一个接受所有字符串的正则表达式，但是在包含两个连续零的任何字符串中，1必须立即跟随ex。它会接受

0
10
01
0010
1111
11001001

但不是

00
000
100

Answer 1

如果我们必须有00后跟1，这意味着以下两件事：

1. 子字符串000不在字符串中
2. 字符串不以后缀00结尾

碰巧的是，上述两个条件也暗示任何00的实例必须后跟1;这些条件是等价的。单独给出条件将使解决此问题变得更容易。

为这种语言写下确定性有限自动机很容易;这样的东西就足够了：

        /---1----\----1---\           /--\
        V        |        |           V   \
----->(q0)--0-->(q1)--0-->(q2)--0-->(q3)  0,1
      \  ^                             \---/
       \1/

(q0)和(q1)国家正在接受并指出(q2)和(q3)不是。 (q3)是一个死亡状态，因为任何带有三个0的字符串在条件1中都不是我们的语言，并且不能兑换。 (q2)不是一个死态，因为我们可以通过添加一个1来修复这个字符串。

有了DFA，我们可以应用已知算法来生成正则表达式。我们可以写下一个系统：

(q0) = e + (q0)1 + (q1)1 + (q2)1
(q1) = (q0)0
(q2) = (q1)0
(q3) = (q2)0 + (q3)(0 + 1)

现在我们要解决(q0)和(q1)，我们的正则表达式将是这两个表达式的并集（+）。我们可以忽略(q3)，因为它不需要并使用替换：

(q0) = e + (q0)1 + (q0)01 + (q2)1
(q1) = (q0)0
(q2) = (q0)00

(q0) = e + (q0)1 + (q0)01 + (q0)001
(q1) = (q0)0
(q2) = (q0)00

(q0) = e + (q0)(1 + 01 + 001)
(q1) = (q0)0
(q2) = (q0)00

(q0) = (1 + 01 + 001)*
(q1) = (1 + 01 + 001)*0
(q2) = (1 + 01 + 001)*00

所以，我们的答案是(1 + 01 + 001)* + (1 + 01 + 001)*0 = (1 + 01 + 001)*(e + 0)。

Answer 2

你可以使用一组嵌套的negative lookahead assertions：

^(?!.*00(?!1)).*

说明：

^      # Anchor the regex to the start of the string
(?!    # Assert that it's impossible to match
 .*    #  any string (caveat: if your string might contain newlines, you need the (?s) modifier)
 00    #  followed by 00
 (?!1) #  unless that is followed by 1
)      # End of lookahead
.*     # This matches the actual string (if the previous lookahead was successful)
       # The .* can be omitted (but then the successful matches will return an empty string)

测试它live on regex101.com。

Answer 3

我不确定自动机的正则表达式，但有点像

^.*001.*$

会匹配

0- 10- 01- 0010- 1111- 11001001- #match
00- 000- 100 #no match
001- 000- 100 #match
00- 000- 1001 #match

说明

• ^匹配线的起点
• .*匹配零和无限次之间的任何字符
• 001匹配文字001
• .*匹配零和无限次之间的任何字符
• $匹配终点线