所以我正在寻找一种方法来编写一个接受所有字符串的正则表达式,但是在包含两个连续零的任何字符串中,1必须立即跟随ex。它会接受
0
10
01
0010
1111
11001001
但不是
00
000
100
如果我们必须有00后跟1,这意味着以下两件事:
碰巧的是,上述两个条件也暗示任何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)
。
你可以使用一组嵌套的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)
我不确定自动机的正则表达式,但有点像
^.*001.*$
会匹配
0- 10- 01- 0010- 1111- 11001001- #match
00- 000- 100 #no match
001- 000- 100 #match
00- 000- 1001 #match
说明
^
匹配线的起点.*
匹配零和无限次之间的任何字符001
匹配文字001.*
匹配零和无限次之间的任何字符$
匹配终点线