我们可以用正则表达式来检查每种类型的字符是否有奇数吗？

Question

问题

我正在尝试创建一个正则表达式，在这个正则表达式中，我们可以检查某个引用集中的所有字母是否都存在于其他字符串中，但只能是奇数（1、3、5，…）。在

以下是代表问题的DFA的（非常）粗略的图像：

我的（破）溶液

我开始使用一个有限集{a, b}，因此我基本上要检查“字符串中是否同时存在as的奇数和{}s的奇数？”在

不幸的是，我自己没有走多远。我第一次读到了this thread，它与这个概念非常相似，但是无法从{}中得到答案。（我知道它是如何工作的，但不知道如何将其转换为检查两个项目的奇数。）

这是我目前为止的想法：^((ab|ba)(bb|aa)?|(bb|aa)?(ab|ba))+$。这基本上检查是否存在ab或ba后跟bb或{}或什么都没有，这将导致ab，ba，abaa，abbb，baaa，或{}。（它也做相反的操作，首先检查双字母）然后可以无限期地重复。我遇到的问题是，如果不同时匹配bbaa，我似乎无法调整它以匹配字符串bbaaba。在

另外，上面的方法不能动态调整以考虑{a, b, c}，尽管我愿意放弃这个来解决初始问题。在

测试

下面是我的测试字符串和所需的输出，括号中有原因：

"ba"      # True (1a, 1b)
"abbb"    # True (1a, 3b)
"bbba"    # True (1a, 3b)
"bbab"    # True (1a, 3b)
"ababab"  # True (3a, 3b)
"bbaaba"  # True (3a, 3b)
"abb"     # False (2b)
"aabb"    # False (2a, 2b)
"aabba"   # False (2b)
""        # False (0a, 0b is "even")
"a"       # False (0b is "even")
"b"       # False (0a is "even")

问题

那么，通过regex实现这一点吗？或者正则表达式比DFA更有限吗？我知道这可以通过一个基本的循环来完成，但这不是我要做的。在

Answer 1

正则表达式的限制不超过DFA；事实上，它们是等价的。（带有反向引用的Perl风格的“regex”更强大，因此它们根本不是“常规的”

如果字符串只包含as，我们可以轻松地编写regex：

a(aa)*

如果其他字母也可能出现在中间，我们仍然可以忽略这些字符：

^{pr2}$

因为regex相当于DFA，所以每个字母都有一个DFA。其实很简单：

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

State（0）是开始状态（“偶数个a出现”），State（（1））是唯一接受的状态（“奇数个as可见”）。如果我们看到一个a，我们将进入另一个状态；对于任何其他字符，我们将保持相同的状态。在

现在DFA的好处是它们是可组合的。特别是在交叉口处是封闭的。这意味着，如果我们有一个能够识别语言“包含奇数个as”的DFA和识别语言“包含奇数bs的字符串”的DFA，我们可以将它们组合成一个能识别这两种语言交集的DFA，也就是说，“包含奇数a和奇数b的字符串”。在

我不想详细介绍这个算法，但是this question有一些很好的答案。得到的DFA将有四种状态：“偶数个as可见，偶数bs已见”，“偶数as可见，奇数bs可见”，等等。在

而且因为dfa等同于regex，所以也存在一个与这些字符串精确匹配的regex。同样，我不会详细介绍算法，但是here is an article可以很好地解释它。为了方便起见，它还附带了一些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)*'

库中可能有一个bug，或者我用错了，因为开头的a*不可能是正确的。但是你得到了一个想法：虽然理论上是可能的，你真的不想为此使用regex！

Answer 2

是的：

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

说明：

^{pr2}$

正则表达式本身不匹配任何字符，因此您将始终获得一个空字符串作为匹配结果（这与将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")

Answer 3

这里有一种方法，使用lookaheads依次断言每个条件。在

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

下面是a demo和您的示例。（演示中的\n用于演示目的。另外，如果只需要测试匹配，而不是捕获，则可以删除(.*)$。）

我将很快添加一个解释。在

---

说明

我们只需要看一半：

^{pr2}$