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

Question

问题

我正在尝试创建一个正则表达式,我们可以检查某些参考集中的所有字母是否都出现在其他字符串中,但只有奇数(1,3,5,...).

这是代表问题的DFA(非常)原始图像:

我的(破碎的)解决方案

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

不幸的是,我自己并没有走得太远.我首先阅读了这个与这个概念非常相似的主题,但未能从中收集答案(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.(它也是相反的,首先检查双字母.)然后可以无限期地重复.我遇到的问题是我似乎无法调整它以匹配字符串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更受限制？我知道它可以通过基本循环完成,但这不是我想要的.

Answer 1

正则表达不仅限于DFA ; 事实上,它们是等价的.(具有反向引用的Perl风格的"正则表达式"严格来说更强大,所以它们根本不是"常规".)

如果字符串只包含as,我们可以轻松编写正则表达式:

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识别语言"包含奇数个as的字符串",另一个识别语言"包含奇数个bs的字符串",我们可以将它们组合成一个识别这两种语言的交集,即"包含奇数个和a' 奇数'的字符串b".

我不会详细介绍算法,但这个问题有一些很好的答案.由此产生的DFA将有四种状态:"偶数as,甚至看到的数量b","偶数as,看到的奇数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*一开始可能不对.但是你明白了这个想法:虽然理论上可行,但你真的不想为此使用正则表达式!

Answer 2

这是一种方法,使用先行来依次断言每个条件.

^(?=[^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.