除了任意数量的 a 和 b 的字符串（如 aa.. 或 bb.. ）之外，正则表达式 (a*+b*) 是否会包含类似的字符串
ab
或任何以 b 结尾的字符串？
(a*+b*) 与 (a* b*) 相同吗？
我对正则表达式 (a*+b*) 生成的字符串有点困惑，如果有人可以提供帮助，我将非常感激。
除非您使用的是明确分类的正则表达式语言*+作为一个特殊的标记，它要么具有特殊的含义，要么为将来的扩展保留（并立即产生定义的行为，或语法错误），自然解析a*+这意味着(a*)+: 后缀+应用于表达式a*.
如果这种解释适用，接下来我们可以观察到(a*)+相当于只是a*。所以a*+b*是相同的a*b*.
首先，根据定义R+ means RR*。匹配一R然后是零个或多个。因此，我们可以重写(a*)+ as (a*)(a*)*.
第二，*是幂等的，所以(a*)*就是只是(a*)。如果我们匹配“零个或多个a”，零次或多次，没有任何变化；净效应为零或多次a. Proof: 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)) into (a|b|c)，当我们对扩展执行此操作时，我们注意到有许多相同的术语 - 空的正则表达式(), 单a， 双aa等等。这些都减少到一个副本，因为(|||)相当于() and (a|a|a|a|...)相当于只是(a)等等。也就是说，当我们通过增加长度对术语进行排序，并将多个相同的术语压缩为一个副本时，我们最终得到(|a|aa|aaa|aaaa|...)，这可以被认为是刚刚的扩展a*. Thus (a*)* is a*.
Lastly, (a*)(a*)只是意味着a*. Proof:与之前类似，我们扩展到分支：(|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*.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
