algorithm - 语言 (a+)* 是否与 a* 相同？

Question

快速提问，如果 a 是正则表达式，那么 a* = (a+)* 是真的吗？

(a+)* 是一个有效的表达式吗？如果是，那么任何人都可以解释为什么它与 a* 相同？我很抱歉在这里问，但我无法通过谷歌找到任何东西。

标签： algorithmregular-language

Answer 1

确实如此L(a*) = L((a+)*)。L(a*)我们可以通过显示是的子集来证明这一点，L((a+)*)反之亦然。

为了证明它L(a*)是一个子集，L((a+)*)我们必须证明任何由生成的东西a*也是由 生成的(a+)*。我们只需要提供一种生成方法。正则表达式a*为所有整数 n 生成字符串 e = a^0, a = a^1, aa = a^2, ..., a^k, ...。a要生成其中任何一个，从子表达式中选择生成的子字符串a+并替换就足够了，这会产生相同的表达式a*，并且显然会以相同的方式生成相同的 a 字符串。

为了证明它L((a+)*)是 的子集L(a*)，我们只需要指出表达式中唯一的字母符号(a+)*是a，因此该表达式只能生成 a 的字符串。因为a*生成了所有这样的字符串，所以同样清楚的L((a+)*)是一个子集或L(a*).

因为L(a*)和L((a+)*)是彼此的子集，所以集合必须相等。也就是说，te 表达式生成相同的语言，因此是等价的。