regex - (a*+b*) 生成的字符串是什么类型

Question

除了任意数量的 a 和 b 的字符串(例如 aa.. 或 bb.. )之外，正则表达式 (a*+b*) 是否会包含类似

的字符串

ab

或任何以 b 结尾的字符串？

(a*+b*) 与 (a* b*) 相同吗？

我对正则表达式 (a*+b*) 生成的字符串有点困惑，如果有人可以提供帮助，我将非常感激。

Answer 1

除非您使用的正则表达式语言明确将 *+ 分类为特殊标记，该标记要么具有特殊含义，要么为将来的扩展保留(并立即产生定义的行为，或者语法错误)，a*+ 的自然解析是它表示 (a*)+:后缀 + 应用于表达式a*。

如果这种解释适用，接下来我们可以观察到 (a*)+ 相当于 a*。因此 a*+b* 与 a*b* 相同。

首先，根据定义，R+ 表示 RR*。匹配一个 R，然后匹配零个或多个。因此，我们可以将(a*)+重写为(a*)(a*)*。

其次，* 是幂等的，因此 (a*)* 只是 (a*)。如果我们匹配“零次或多次a”，零次或多次，则不会发生任何变化；最终效果是零个或多个a。 证明: R* 表示无限扩展: (|R|RR|RRR|RRRR|RRRRR|...):不匹配任何内容，或匹配一个 R，或匹配两个 R，...因此，(a*)* 削弱了此扩展: (|a*|a*a*|a*a*a*|...)。这些内部 a*-s 依次表示各个二级扩展:(|(|a|aa|aaa|...|)|(|a|aa|aaa|. ..)(a|a|aaa|...))|...)。通过分支|的关联属性，我们可以将(a|(b|c))这样的结构扁平化为(a|b|c)，当我们对扩展进行此操作时，我们注意到有许多相同的术语 - 空的正则表达式 ()、单个 a、双 >aa 等等。这些都简化为单个副本，因为 (|||) 相当于 () 和 (a|a|a|a|...) 相当于 (a) 等等。也就是说，当我们通过增加长度对术语进行排序，并将多个相同的术语压缩为一个副本时，我们最终得到 (|a|aa|aaa|aaaa|...)，它可以被识别为 a* 的扩展。因此 (a*)* 是 a*。

最后，(a*)(a*) 仅表示a*。 证明:与之前类似，我们扩展到分支:(|a|aa|aaa|...)(|a|aa|aaa|...) 。接下来我们注意到分支表达式的串联相当于项的笛卡尔积集。也就是说 (a|b|c|..)(i|j|k|...) 准确地说是: (ai|aj|ik|...| bi|bj|bk|...|ci|cj|ck|...|...)。当我们将此乘积应用于 (|a|aa|aaa|...)(|a|aa|aaa|...) 时，我们会得到大量术语，这些术语按递增排列时长度并进行重复数据删除，减少为 (|a|aa|aaa|aaaa|...)，这只是 a*。