Регулярное выражение, которое принимает строки, в которых после каждых двух нулей следует единица

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) является мертвым состоянием, поскольку любая строка с тремя нулями отсутствует в нашем языке по условию 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

Для этого можно использовать набор вложенных отрицательных прогнозных заявлений :

^(?!.*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)

Проверить это жить на 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
• .* соответствует любому символу от нуля до бесконечного времени
• $ соответствует концу строки