Можем ли мы использовать регулярные выражения для проверки наличия нечетного числа каждого типа символов?

Ответ 1

Здесь один из способов сделать это, используя lookaheads для утверждения каждого условия в свою очередь.

^(?=[^a]*a(?:[^a]*a[^a]*a)*[^a]*$)(?=[^b]*b(?:[^b]*b[^b]*b)*[^b]*$)(.*)$

Здесь демонстрация с вашими примерами. (\n в демонстрации предназначены для целей презентации. Также вы можете отказаться от (.*)$, если вам нужно только проверить совпадение, а не снимать.)

Я скоро добавлю объяснение.

Объяснение

Нам нужно только посмотреть на половину:

(?=  [^a]*a  (?:[^a]*a[^a]*a)  *  [^a]*$  )
|    |       |                 |  |
|    |       |                 |  Only accept non-'a to the end.
|    |       |                 |
|    |       |                 Zero or more of these pairs of 'a's.
|    |       |
|    |       Strictly a pair of 'a's.
|    |
|    Find the first 'a'.
|
Use a lookahead to assert multiple conditions.

Ответ 2

Режимы не более ограничены, чем DFA; на самом деле они эквивалентны. ( "Регулярные выражения в стиле Perl" с обратными ссылками являются более сильными, поэтому они не являются "регулярными" вообще.)

Мы можем легко написать регулярное выражение, если строка содержит только a s:

a(aa)*

И если между ними также могут встречаться другие буквы, мы все равно можем это сделать, просто игнорируя эти символы:

[^a]*a([^a]*a[^a]*a)*[^a]*

Поскольку регулярные выражения эквивалентны DFA, у нас есть DFA для каждой из отдельных букв. Это довольно просто, на самом деле:

 [^a] _      [^a] _
     / \         / \
     | v   a     | v
---> (0) -----> ((1))
         <-----
            a

Состояние (0) - это начальное состояние ( "четное число a видно" ), а состояние ((1)) является единственным принимающим состоянием ( "нечетное число a видно" ). Если мы увидим a, перейдем к другому состоянию; для любого другого символа мы остаемся в том же состоянии.

Теперь хорошая вещь о DFA заключается в том, что они являются составными. В частности, они закрываются при пересечении. Это означает, что если у нас есть DFA, который распознает строку "string", содержащую нечетное число a s ", а другой, который распознает строку языка, содержащую нечетное число b s", мы можем объединить их в DFA, который распознает пересечение этих двух языков, то есть "строка, содержащая нечетное число a и нечетное число b" s.

Я не буду вдаваться в подробности об алгоритме, но этот вопрос содержит некоторые довольно хорошие ответы. В результате DFA будет иметь четыре состояния: "четное число a, четное число b замечено", "четное число a, нечетное число b замечено" и т.д.

И поскольку DFA эквивалентны регулярным выражениям, существует также регулярное выражение, которое соответствует именно этим строкам. Опять же, я не буду вдаваться в подробности об алгоритме, но вот статья, которая объясняет это довольно хорошо. Удобно, что он также поставляется с кодом Python 3 для выполнения грязной работы:

>>> from fsm import fsm
>>> a = fsm(
      alphabet = {'a', 'b'},
      states = {0, 1, 2, 3},
      initial = 0,
      finals = {3},
      map = {
        0: {'a': 1, 'b': 2},
        1: {'a': 0, 'b': 3},
        2: {'a': 3, 'b': 0},
        3: {'a': 2, 'b': 1}
      }
    )
>>> str(a.lego())
'a*(ab|b(ba*b)*(a|ba+b))((a|ba+b)(ba*b)*(a|ba+b)|ba*b)*'

В библиотеке может быть ошибка, или я использую ее неправильно, потому что a* в начале не может быть прав. Но вы получаете идею: хотя это теоретически возможно, , вы действительно не хотите использовать регулярные выражения для этого!

Ответ 3

Да:

^(?=b*(?:ab*ab*)*ab*$)(?=a*(?:ba*ba*)*ba*$)

Объяснение:

^             # Start of string
(?=           # Assert that it possible to match
 b*           # any number of 'b's
 (?:ab*ab*)*  # followed by an even number of 'a with optional 'b in-between
 ab*          # followed by one 'a' and optional 'b's
 $            # until the end of the string.
)             # End of lookahead
(?=a*(?:ba*ba*)*ba*$)  # Same thing, vice versa

Само регулярное выражение не соответствует никаким символам, поэтому вы всегда получите пустую строку в качестве результата соответствия (которая отличается от получения None в качестве результата сопоставления):

>>> import re
>>> re.match("^(?=b*(?:ab*ab*)*ab*$)(?=a*(?:ba*ba*)*ba*$)", "ab")
<_sre.SRE_Match object at 0x00000000022AA7E8>
>>> re.match("^(?=b*(?:ab*ab*)*ab*$)(?=a*(?:ba*ba*)*ba*$)", "aab")