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

Question

问题

我正在尝试创建一个正则表达式，我们可以在其中检查某个引用集中出现的所有字母是否出现在其他某个字符串中，但仅限于奇数(1、3、5、...)。

这是 DFA 的(非常)粗略的图像表示问题:

我的(损坏的)解决方案

我开始使用有限集 {a, b}，所以我基本上会检查“是否同时存在奇数个 a 和奇数个b在字符串中？"

不幸的是，我自己并没有走多远。我第一次阅读this thread ，这与这个概念非常相似，但无法从 (aa|bb|(ab|ba)(aa|bb)*(ba|ab))*(b|(ab| ba)(bb|aa)*a)。 (我了解它是如何工作的，但不知道如何将其转换为检查 两个 项目的奇数。)

这是我到目前为止的想法:^((ab|ba)(bb|aa)?|(bb|aa)?(ab|ba) )+$。这基本上检查是否有 ab 或 ba 后跟 bb 或 aa 或什么都没有，这将导致 ab、ba、abaa、abbb、baaa 或 babb。 (它也做相反的事情，首先检查双字母。)然后可以无限期地重复。我遇到的问题是，如果不匹配 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")

问题

那么，这可以通过正则表达式实现吗？还是正则表达式比 DFA 更受限制？我知道它可以通过一个基本循环来完成，但这不是我想要的。

Answer 1

正则表达式并不比 DFA 更受限制;事实上，它们是等价的。 (具有反向引用的 Perl 风格的“正则表达式”严格来说更强大，所以它们根本不是“常规”的。)

如果字符串只包含a，我们可以轻松编写正则表达式小号:

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 的好处在于它们可组合。特别是，它们在交叉路口下是封闭的。这意味着，如果我们有一个识别语言“包含奇数个 a 的字符串”的 DFA，另一个识别语言“包含奇数个 b 的字符串”的 DFA，我们可以将它们组合起来到识别这两种语言交集的 DFA，即“包含奇数个 a 和奇数个 b 的字符串”。

我不会详细介绍算法，但 this question有一些很好的答案。生成的 DFA 将有四种状态:“看到偶数个a，看到偶数个b”，“看到偶数个a，看到奇数个b”，等等。

并且由于 DFA 等同于正则表达式，因此还存在一个与这些字符串精确匹配的正则表达式。同样，我不会详细介绍算法，但是 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)*'

库中可能存在错误，或者我使用错误，因为 a*一开始不可能是对的。但您明白了:虽然理论上可行，但您真的不想为此使用正则表达式!