(a*+b*) 生成的字符串类型是什么
What are the type of Strings generated by (a*+b*)
除了像 aa.. 或 bb.. 这样的任意数量的 a 和 b 的字符串之外，正则表达式 (a*+b*) 是否会包含像
这样的字符串
ab
或任何以 b 结尾的字符串？
(a*+b*) 和 (a* b*) 一样吗？
我对正则表达式 (a*+b*) 生成的字符串有点困惑，如果有人能提供帮助，我将不胜感激。
我认为这有助于查看正则表达式的正式定义，即查找每个正则表达式 e 它产生的语言 L(e)。
那么让我们从简单的开始：
(1)
正则表达式 a （只有字母）怎么样？它的语言是
L(a) := {a},
只是单身 word/character "a".
(2)
对于正则表达式 e1 + e2，其中 e1 和 e2 本身就是正则表达式，
L(e1 + e2) := L(e1) U L(e2).
例如如果 a 和 b 是字符，L(a+b) = {a, b}.
(3)
对于正则表达式 e1 e2（连接），其中 e1 和 e2 本身就是正则表达式，
L(e1 e2) := all words w such that
we can write w = w_1w_2 with w_1 in L(e1) and w_2 in L(e2)".
(4)
正则表达式 *e** 怎么样，其中 e 本身可能是正则表达式？直觉上，如果一个词具有以下形式，它就在 L(e*) 中
w_1 w_2w_3w_4...w_n，每个 i 的 L(e) 中有 w_i。
所以
L(e*) := all words w such that we can write
w = w_1 w_2 .. w_n
for a n >= 0 with all w_i in L(e) (for i = 1, 2, ..., n)
那么，L((a* + b*)) 呢？
L((a* + b*))
(according to rule 2)
= L(a*) U L(b*)
(according to rule 4/1)
= {eps, a, aa, aaa, aaaa, ....} U {eps, b, bb, bbb, bbbb}
= all strings that have either only a's OR only b's in it
(including eps, the so-called empty word)
与 (a* b*) 类似：
L((a* b*))
(according to rule 3)
= all words w = w_1 w_2 with w_1 in L(a*) and w_2 in L(b*)
= {eps eps, eps b, a eps, ab, aa eps, aab, ...}
= {eps, b, a, ab, aa, aab, aabb, ... }
= all strings that first have zero or more a's, then zero or more b's.
一开始我认为它有助于 "deconstruct" 正则表达式，就像我们上面所做的那样 - 因为正则表达式也可以看作树，就像更广为人知的算术表达式一样，例如：
+
/ \
* *
| |
a b
除非您使用的正则表达式语言明确地将 *+ 分类为具有特殊含义或保留用于将来扩展的特殊标记（并现在产生定义的行为，或语法错误），a*+ 的自然解析是它的意思是 (a*)+：后缀 + 应用于表达式 a*.
如果该解释适用，接下来我们可以观察到 (a*)+ 等价于 a*。因此 a*+b* 与 a*b* 相同。
首先，根据定义 R+ 表示 RR*。匹配一个 R，然后匹配零个或多个。因此，我们可以将(a*)+重写为(a*)(a*)*.
其次，*是幂等的，所以(a*)*就是(a*)。如果我们匹配 "zero or more a" 零次或多次，则没有任何变化；净效应为零或更多 a。 证明： R*表示这个无限展开：(|R|RR|RRR|RRRR|RRRRR|...)：不匹配，或者匹配一个R，或者匹配两个R的, ... 因此，(a*)* 削弱了这个扩展：(|a*|a*a*|a*a*a*|...)。这些内部 a*-s 依次表示单个 second-level 扩展：(|(|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|...) 时，我们得到了术语的激增，当以增加的长度排列并受 de-duplication 约束时，减少到 (|a|aa|aaa|aaaa|...)，这就是 a*.
除了像 aa.. 或 bb.. 这样的任意数量的 a 和 b 的字符串之外，正则表达式 (a*+b*) 是否会包含像
这样的字符串ab
或任何以 b 结尾的字符串？
(a*+b*) 和 (a* b*) 一样吗？
我对正则表达式 (a*+b*) 生成的字符串有点困惑，如果有人能提供帮助，我将不胜感激。
我认为这有助于查看正则表达式的正式定义，即查找每个正则表达式 e 它产生的语言 L(e)。
那么让我们从简单的开始：
(1) 正则表达式 a （只有字母）怎么样？它的语言是
L(a) := {a},
只是单身 word/character "a".
(2) 对于正则表达式 e1 + e2，其中 e1 和 e2 本身就是正则表达式，
L(e1 + e2) := L(e1) U L(e2).
例如如果 a 和 b 是字符，L(a+b) = {a, b}.
(3) 对于正则表达式 e1 e2（连接），其中 e1 和 e2 本身就是正则表达式，
L(e1 e2) := all words w such that
we can write w = w_1w_2 with w_1 in L(e1) and w_2 in L(e2)".
(4) 正则表达式 *e** 怎么样，其中 e 本身可能是正则表达式？直觉上，如果一个词具有以下形式，它就在 L(e*) 中 w_1 w_2w_3w_4...w_n，每个 i 的 L(e) 中有 w_i。 所以
L(e*) := all words w such that we can write
w = w_1 w_2 .. w_n
for a n >= 0 with all w_i in L(e) (for i = 1, 2, ..., n)
那么，L((a* + b*)) 呢？
L((a* + b*))
(according to rule 2)
= L(a*) U L(b*)
(according to rule 4/1)
= {eps, a, aa, aaa, aaaa, ....} U {eps, b, bb, bbb, bbbb}
= all strings that have either only a's OR only b's in it
(including eps, the so-called empty word)
与 (a* b*) 类似：
L((a* b*))
(according to rule 3)
= all words w = w_1 w_2 with w_1 in L(a*) and w_2 in L(b*)
= {eps eps, eps b, a eps, ab, aa eps, aab, ...}
= {eps, b, a, ab, aa, aab, aabb, ... }
= all strings that first have zero or more a's, then zero or more b's.
一开始我认为它有助于 "deconstruct" 正则表达式，就像我们上面所做的那样 - 因为正则表达式也可以看作树，就像更广为人知的算术表达式一样，例如：
+
/ \
* *
| |
a b
除非您使用的正则表达式语言明确地将 *+ 分类为具有特殊含义或保留用于将来扩展的特殊标记（并现在产生定义的行为，或语法错误），a*+ 的自然解析是它的意思是 (a*)+：后缀 + 应用于表达式 a*.
如果该解释适用，接下来我们可以观察到 (a*)+ 等价于 a*。因此 a*+b* 与 a*b* 相同。
首先，根据定义 R+ 表示 RR*。匹配一个 R，然后匹配零个或多个。因此，我们可以将(a*)+重写为(a*)(a*)*.
其次，*是幂等的，所以(a*)*就是(a*)。如果我们匹配 "zero or more a" 零次或多次，则没有任何变化；净效应为零或更多 a。 证明： R*表示这个无限展开：(|R|RR|RRR|RRRR|RRRRR|...)：不匹配，或者匹配一个R，或者匹配两个R的, ... 因此，(a*)* 削弱了这个扩展：(|a*|a*a*|a*a*a*|...)。这些内部 a*-s 依次表示单个 second-level 扩展：(|(|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|...) 时，我们得到了术语的激增，当以增加的长度排列并受 de-duplication 约束时，减少到 (|a|aa|aaa|aaaa|...)，这就是 a*.