“(a+b)*”和“(a*b*)*”有什么区别？

Question

假设 Σ = {a, b}，我想找到正则表达式（RE）Σ*（表示字母表 Σ 上的所有可能字符串集合）。

我提出了以下两种可能性：

(a+b)*
(a*b*)*

然而，我自己无法决定哪个正则表达式是正确的，或者两者都不好。请告诉我正确答案。

- Rurou2

---

后者是正确的。前者需要至少一个a在每个b之前，所以例如字符串b不会匹配。 - kaya3

如果这是在计算机科学的上下文中 - 形式语言和自动机 - 忽略paxdiablo的答案，使用Welbog的答案。 - Patrick87

Answer 1

+ 运算符通常在学术正则表达式中用于表示联合 (|, "或")，而在非学术正则表达式（例如大多数正则表达式实现）中，它通常表示"一个或多个"，而不是"或"。

因此，a+b 表示 [ab] 或 a|b，因此 (a+b)* 表示长度为 0 或更多的任意字符串，其中包含任意数量的 a 和 b，顺序任意。

同样，(a*b*)* 也表示长度为 0 或更多的任意字符串，其中包含任意数量的 a 和 b，顺序任意。

这两个表达式是表示相同语言的不同方式。

- Welbog

---

“汽车”和“自动动力机械设备”（汽车的希腊语为αυτοκίνητο（发音为'aftokinito'））这两个描述词也可以指同一物品，但我认为我更喜欢前者。并不是贬低你的答案，只是建议使用(a+b)*而非另一个 :-) - paxdiablo

Answer 2

在正则表达式语法中，(a+b)* 表示以 a 开头，后跟零或多个 a，最后是一个 b 的任意序列，不包括像 baa（它不以 a 开头），abba 和 a（每个 a 组后必须有一个 b），因此它是不正确的。

而 (a*b*)* 表示包含零或多个 a，接着是零或多个 b 的任意序列，可以以任何字符作为起始字符且字符的顺序和数量都可以任意组合。这种表示方法更加正确，并且允许空字符串，我相信 Σ* 也应该允许空字符串（但这取决于您的需求）。

然而，更简单的做法可能是选择 [ab]*（如果您认为空字符串无效，则可以选择 [ab]+）。这基本上表示从类 [ab] 中任选零个或多个字符（对于 + 变体来说至少选一个）。

---

然而，由于您使用了 Σ，所以您可能正在讨论 形式化 语言理论（其中 Σ 很常见），而不是正则表达式语法（其中它往往不被使用）。

如果确实是这样的情况，那么您应该了解在形式化语言中有一些变体，其中 a | b 表达式（在正则表达式语法中相当于 [ab]）可以替换为 a ∪ b、a ∨ b 或 a + b 中的任何一个运算符符号，每个运算符符号都表示“逻辑或”。

这意味着对于您需要的内容来说，(a+b)* 实际上是正确的（因为它等价于我上面给出的正则表达式语法），因为它基本上表示来自集合 {a, b} 的任意字符，重复零次或多次。

此外，您的 (a*b*)* 选项也涵盖了它，但通常最好选择最简单的解决方案 :-)

---

还有一些其他要记住的事情，对于形式化语言的情况。在英语中，"a" 是一个单词，但你很难找到支持 "" 也是一个单词的人。尝试在字典中查找 :-)

换句话说，任何允许语言字符的空序列（比如(a+b)*）的正则表达式可能不适合。你可能会发现(a+b)(a+b)*是一个更好的选择。这取决于Σ*是否允许空序列。

- paxdiablo

Answer 3

根据正则表达式的代数性质，

(a*b*)* = (a+b)*

因此，(a+b)* = (a*b*)* 额外信息：

(a+b)* = L(a+b)*
       = (L(a+b))*
       = (L(a) U L(b))*
       = ({a} U {b})*
       = {a,b}*
       = {ε, a, b, aa, bb, ab, abab, aba, bbba,...}

- Kasun