regex - 正则表达式等价

Question

下面的正则表达式等价是真的吗？为什么或者为什么不？

(ab)* u (aba)* = (ab u aba)*

*=克莱恩星

u=并集（集合论）

Answer 1

不，它们不相等。RHS 上的语言包含“abaab”，但 LHS 上的语言没有。这些之间有什么关系吗？是的; 但我不会只给你答案。提示：RHS 中有没有 LHS 中没有的字符串？

编辑：

只是为有兴趣的读者解释一下。语言是字符串的集合。因此，集合之间的关系也是语言之间的关系。最常见的集合关系是等式、子集和超集。给定两个集合 A 和 B 在全集 U1 和 U2 上，集合 A 是全集 U1 u U2 下 B 的子集（u 代表并集）当且仅当 A 的每个元素也是 B 的元素。类似地，给定两个集合 A和 B 在全集 U1 和 U2 上，集 A 是全集 U1 u U2 下 B 的超集（u 代表并集）当且仅当 B 的每个元素也是 A 的元素（等效地，当且仅当 B 是 A 的子集） . 如果 A 是 B 的子集且 B 是 A 的子集，则集合 A 和 B 相等（等效地，如果 A 是 B 的超集且 B 是 A 的超集）。请注意，两个集合 A 和 B 不需要处于这三个关系中的任何一个；

要查找集合 A 和 B 之间存在四种可能关系中的哪一种 - 相等、子集、超集、无 - 您通常检查 A 是否是 B 的子集以及 B 是否是 A 的子集。调用第一个检查 B1 和第二个检查检查 B2，其中 B1 和 B2 是布尔变量，并且当检查通过时为真（即，在 B1 的情况下，A 是 B 的子集，在 B2 的情况下，B 是 A 的子集）。那么 (B1 && B2) 对应相等， (B1 && !B2) 对应子集， (!B1 && B2) 对应超集， (!B1 && !B2) 对应无关系。

在上面的示例中，我通过证明 RHS 包含不在 LHS 中的元素来证明两种语言不相等。请注意，这也排除了“A 是 B 的超集”关系。剩下两个：B 是 A 的超集，或者它们之间没有关系。要确定这一点，您必须确定 A 是否是 B 的子集；LHS 语言中的元素是否都在 RHS 语言中。如果是，则 LHS 是一个子集；否则，没有关系。

为了证明一个集合中有一个元素而不是另一个，最简单和最有说服力的方法是通过反例证明：在一个集合中命名一个字符串，而不是另一个。这是我采用的方法。您还可以论证语言必须包含这样的元素，而无需明确命名它；这种证明可能更难正确。

为了证明集合 A 的每个元素也在集合 B 中，您将需要更通用的证明技术。归纳证明和矛盾证明是常见的例子。要进行归纳证明，您可以显式或隐式地为语言中的每个字符串分配一个自然数，用一个简单的参数证明您的主张（在这种情况下，该元素也是另一个集合的元素）是正确的. 然后，您假设集合中的前 n 个元素是正确的（根据您给出的编号），并表明这意味着后面的所有元素也必须满足您的要求。要通过矛盾进行证明，您假设与要证明的内容相反，并得出矛盾。如果你成功了并且你唯一的假设是你的主张是错误的，那么你的主张一定一直都是真的。

Answer 2

不，它们不相等。

相似之处：

1. 都接受空字符串
2. 都接受“ababa” （regex2的最小表达）

差异：

1. ab和aba可能在regex1中出现一次或不出现，与regex2不同，它们可能出现或不出现，但在连词中出现。

既然我们有区别，我们可以说它们是不等价的。

但

由于正则表达式是正则语言的表示（不是描述），因此您不能仅通过查看表达式就知道regex1等同于regex2 ，为了证明它（数学证明），您可以将这些正则表达式转换为NFA（非确定性有限自动机）或 DFA（确定性有限自动机）并比较差异。