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

Question

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

我想出了以下两个 RE（正则表达式）

(a+b)*

(a*b*)*

但是，我不能自己决定哪个 RE 是正确的，或者两个都不好。所以，请告诉我正确答案。

Answer 1

在正常的正则表达式语法中，(a+b)* 表示零个或多个以 a 开头的任何序列，然后有零个或多个 a，然后是 b .这会打折诸如 baa（它不以 a 开头）、abba 和 a（必须有一个 exactly b 在每个 a 组之后），所以是不正确的。

(a*b*)* 表示包含零个或多个 a 后跟零个或多个 b 的任何序列的零个或多个。这是更正确的，因为它允许起始字符、字符的任意顺序和数量等等。它还允许空字符串，我很确定 Σ* 应该允许它（但我会把它留给你）。

但是，最好选择更简单的 [ab]*（或 [ab]+，以防万一您认为空字符串无效）。这基本上是零（一个用于 + 变体）或更多从 class [ab].

中提取的任何字符

但是，有可能，因为您使用的是Σ，您可能正在讨论正式语言理论（其中 Σ 是常见的）而不是正则表达式语法（它往往不是）。

如果是的情况，那么您应该了解形式语言的变体，其中 a | b 表达式（在正则表达式语法中有效 [ab] ) 可以改为呈现为 a ∪ b、a ∨ b 或 a + b 之一，其中每个运算符符号代表 "logical or".

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

此外，也包含在您的 (a*b*)* 选项中，但选择最简单的选项几乎总是更好:-)

Answer 2

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

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

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

这两种表达方式是同一种语言的不同表达方式。

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,...}

What is the difference between (a+b)* and (ab)*?