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

问题描述 投票:1回答:3

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

0
10
01
0010
1111
11001001

但不是

00
000
100
regex automata
3个回答
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)


0
投票

你可以使用一组嵌套的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


-1
投票

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

^.*001.*$

会匹配

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

说明

  • ^匹配线的起点
  • .*匹配零和无限次之间的任何字符
  • 001匹配文字001
  • .*匹配零和无限次之间的任何字符
  • $匹配终点线
© www.soinside.com 2019 - 2024. All rights reserved.