是的,这样的字符串集合是存在的。 我们可以构建出这样的集合,它的核心在于我们能够创造出一些“陷阱”,让任何试图用一个单一的、固定的正则表达式来捕捉所有这些字符串的尝试都必然失败。
想象一下,我们想要定义一个集合,里面包含所有由字母 'a' 和 'b' 组成的字符串,但有一个非常特殊的限制:任何以 'aa' 开头的字符串,其长度都必须是偶数。而任何不以 'aa' 开头的字符串,则没有长度上的限制。
现在,我们来尝试构建一个正则表达式来匹配这个集合。
首先,我们考虑不以 'aa' 开头的字符串。这部分相对容易处理。它们可以由任意数量的 'a' 或 'b' 组成,只要第一个字符不是 'a',或者第一个是 'a' 但第二个不是 'a'。
如果字符串以 'b' 开头,那么后面可以是任意的 'a' 或 'b' 组成的字符串。这可以用 `b(a|b)` 来表示。
如果字符串以 'a' 开头,但第二个字符不是 'a',那它就是 'ab' 开头,或者 'a' 本身(如果长度是1)。 所以,它可能是 `a(b|a(b|a))`。 这也可以写成 `a(b|a(b|a))`。 换句话说,如果不是 `aa` 开头,那它就不能同时以 `a` 开头且第二个字符也是 `a`。
我们把这两部分结合起来,考虑不以 'aa' 开头的字符串:
`b(a|b) | a(b|a)`
这里 `a(b|a)` 实际上会匹配所有以 'a' 开头的字符串,除非后面紧跟着一个 'a'。所以,这可以更简洁地写成:
`b(a|b) | a[^a](a|b)` (这里 `[^a]` 是“不是a”的简写,虽然正则表达式的标准写法不是这样,但为了表达意思)。
更精确地说,我们可以表示为:
`b(a|b) | a(b|a)` 这里的 `a(b|a)` 已经包含了所有以 a 开头,但后面不是 a 的情况。
现在,我们来看以 'aa' 开头的字符串。根据我们的规则,它们必须是偶数长度。
例如:
`aa` (长度 2)
`aaaa` (长度 4)
`aabbaa` (长度 6)
如何用正则表达式表示“以 'aa' 开头且长度为偶数”?
“以 'aa' 开头”是 `^aa`。
“长度为偶数”意味着后面跟着偶数个字符。
我们可以表示为 `aa(aa|bb|ab|ba)`? 不,这只是包含了特定偶数长度的例子。
更通用地说,偶数长度可以通过成对的字符来实现。
例如:`aa` 后面跟着任意两个字符(`aa`,`ab`,`ba`,`bb`),然后重复。
所以,`aa(aa|ab|ba|bb)` 可以表示以 'aa' 开头,后面跟着偶数个字符。
但我们也可以有 `aa` 后面跟着 `aab` 这样的奇数个字符,总长度是 5,这是不符合规则的。
规则是:整个字符串必须是偶数长度。
所以,对于以 'aa' 开头的字符串,我们必须确保整个字符串是偶数长度。
这可以通过 `aa` 后面跟着成对的字符来实现,比如 `aa((a|b)(a|b))` 。
这里 `(a|b)(a|b)` 代表任意两个字符,重复任意次数,加上开头的 `aa`,总长度总是偶数。
所以,以 'aa' 开头的偶数长度字符串可以表示为: `^aa((a|b)(a|b))$`
现在,我们把整个集合的描述结合起来:
1. 不以 'aa' 开头的任意长度字符串。
2. 以 'aa' 开头且长度为偶数的字符串。
我们之前描述不以 'aa' 开头的字符串为 `b(a|b) | a(b|a)`。
而以 'aa' 开头的偶数长度字符串是 `aa((a|b)(a|b))$`。
将这两部分合并:
`^(b(a|b)|a(b|a)|aa((a|b)(a|b)))$`
看起来我们好像找到了一个正则表达式。但问题在于,这种“一个正则表达式”的表述,在逻辑上是有缺陷的,因为我们描述的是两种互斥的条件。
条件一:字符串不以 'aa' 开头。
条件二:字符串以 'aa' 开头且长度为偶数。
任何一个字符串要么满足条件一,要么满足条件二。
如果我们试图构造一个正则表达式来同时匹配这两类字符串,我们似乎成功了。
然而,我们要探讨的是,是否存在一个集合,不存在一个正则表达式仅匹配这个集合中的字符串。
我的例子中,是不是已经找到了一个集合,并且我们找到了一个正则表达式?
问题的关键在于“仅匹配”。 如果我的正则表达式 `^(b(a|b)|a(b|a)|aa((a|b)(a|b)))$` 能够准确无误地捕捉所有满足我们定义的字符串,并且不会捕捉任何不满足的字符串,那么这个集合是可以被一个正则表达式匹配的。
让我们仔细审视我的定义:
“任何以 'aa' 开头的字符串,其长度都必须是偶数。而任何不以 'aa' 开头的字符串,则没有长度上的限制。”
这个定义本身并不提供一个“不存在”的集合。我的例子是可以被一个正则表达式描述的。
要创造一个“不存在”的集合,我们需要利用正则表达式的局限性,或者说,利用某些计算理论中的不可判定性。
一个经典的例子可以说明这一点,虽然它不是关于字符串集合本身,而是关于正则表达式能否匹配某个特定字符串。
考虑一个集合 S,其中包含所有由 '0' 和 '1' 组成的字符串,并且这些字符串代表着一个无法被任何有限状态自动机(FSA)识别的语言。 FSA 是正则表达式的等价物。
例如,考虑语言 L = { $0^n1^n$ | n ≥ 0 },即形如 "01", "0011", "000111" 等的字符串。
任何 FSA 识别这个语言都需要一种方法来“计数”0的数量,并将其与1的数量进行匹配。 FSA 只有有限的内存(状态),因此无法无限计数。 因此,L 是一个不可正则语言。
我们能否构建一个集合,使得它就是一个不可正则语言?
是的。 字符串集合 S 可以被定义为:
S = { w | w 是一个字符串,w 编码了一个图灵机 M,且 M 在输入 w 时会进入死循环 }
图灵机是否在给定输入下进入死循环是一个不可判定的问题。 也就是说,不存在一个算法(或一个正则表达式,作为 FSA 的等价物)能够“总是”判断一个字符串是否属于这个集合。
这个集合 S 的字符串就是那些“编码了死循环图灵机的字符串”。 如果我们假设一个图灵机可以被编码成一个字符串(例如,通过其指令集和状态的序列化),那么这个集合 S 的定义就是有效的。
为什么没有一个正则表达式能仅匹配这个集合?
正则表达式的能力限制: 正则表达式描述的是正则语言。正则语言的特点是可以通过有限状态自动机(FSA)识别。FSA 具有有限的内存(状态),它们无法执行无限的计数或记忆。
“死循环”的不可判定性: 判断一个图灵机是否会在一个特定输入下死循环,这是一个著名的计算理论中的“停机问题”的变种,它是不可判定的。 这意味着,不存在一个通用的算法(更不用说一个有限状态的 FSA 或一个等价的正则表达式)可以完美地识别所有“死循环”的图灵机编码,而忽略其他所有字符串。
“编码”带来的复杂性: 我们讨论的不是简单的字符模式,而是“字符串本身是否代表了一个导致死循环的计算过程”。 这种“元”层面的描述,即字符串的内容对字符串本身的归属起着决定性作用,并且这种决定需要模拟一个可能无限进行的计算,超出了正则表达式的范畴。
所以,这个字符串集合 S 的描述是:
S 是所有字符串的集合,其中每个字符串都编码了这样一个图灵机 M,并且当 M 在其自身的编码作为输入时,M 会永远运行下去,不会停止。
任何声称能匹配这个集合 S 的正则表达式,都将隐含地声称能够解决“图灵机停机问题”,而这是不可能的。 因此,这样的正则表达式根本就不存在。
这个集合 S 是存在的,并且它是一个不可正则语言。 因此,不存在一个正则表达式能仅匹配这个集合中的字符串。 任何试图构造这样一个正则表达式的尝试,最终都会发现,要么它匹配了不该匹配的字符串(即不是死循环图灵机编码的字符串),要么它遗漏了某些属于集合 S 的字符串(即死循环图灵机编码的字符串)。