15

问题

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

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

奇数 A 和 Bs DFA

我的（损坏的）解决方案

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

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

到目前为止，这是我想出的：^((ab|ba)(bb|aa)?|(bb|aa)?(ab|ba))+$。这基本上检查是否有aborba后跟bbor aaor nothing，这将导致ab, ba, abaa, abbb, baaa, or babb。（它也做与此相反的操作，首先检查双字母。）然后可以无限期地重复。我遇到的问题是我似乎无法调整它以匹配字符串bbaaba而不匹配bbaa。

另外，上面的方法不能动态调整{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 更受限制？我知道它可以通过一个基本循环来完成，但这不是我想要的。

4

3 回答 3

11

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

a如果字符串仅包含s ，我们可以轻松编写正则表达式：

a(aa)*

如果中间也可能出现其他字母，我们仍然可以通过简单地忽略这些字符来做到这一点：

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

因为正则表达式等同于 DFA，所以我们对每个单独的字母都有一个 DFA。其实很简单：

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

状态 (0) 是开始状态（“看到偶数个as”），状态 ((1)) 是唯一接受状态（“看到奇数个as”）。如果我们看到一个a，我们就进入另一个状态；对于任何其他角色，我们保持相同的状态。

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

我不会详细介绍算法，但这个问题有一些很好的答案。生成的 DFA 将具有四种状态：“a看到偶数个 s，看到偶数个bs”，“a看到偶数个 s，看到奇数个bs”等等。

由于 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*开始不可能是正确的。但是你明白了：虽然理论上可行，但你真的不想为此使用正则表达式！

于 2012-09-14T21:00:18.817 回答
8

这是一种方法，使用前瞻依次断言每个条件。

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

这是一个带有您的示例的演示。（\n演示中的 s 用于演示目的。此外，(.*)$如果您只需要测试匹配而不是捕获，则可以删除。）

我将很快添加一个解释。

解释

我们只需要看一半：

(?=  [^a]*a  (?:[^a]*a[^a]*a)  *  [^a]*$  )
|    |       |                 |  |
|    |       |                 |  Only accept non-'a's 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.
于 2012-09-14T20:37:45.953 回答
4

是的：

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

解释：

^             # Start of string
(?=           # Assert that it's possible to match
 b*           # any number of 'b's
 (?:ab*ab*)*  # followed by an even number of 'a's with optional 'b's 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")
于 2012-09-14T20:39:02.240 回答