concatenation - 如果一个正则语言只包含 Kleene 星，那么它有可能来自两个非常规语言的串联吗？

Question

我想知道，给定一个只包含 Kleene 星号运算符（例如（ab）*）的常规语言 L，是否可以通过连接两种非常规语言来生成 L？我试图证明 L 只能由两种常规语言的连接生成。

谢谢。

Answer 1

这种说法是错误的。在 Σ = {a} 上考虑这两种语言：

L ₁ = { 一个ⁿ | n 是 2 的幂 } ∪ { ε }

L ₂ = { 一个ⁿ | n不是2 的幂 } ∪ { ε }

这两种语言都不是正则的（第一种可以通过 Myhill-Nerode 定理证明是非常规的，而第二种与 L ₁的补码密切相关，也可以证明是非常规的。

但是，我要声明 L ₁ L ₂ = a*。首先，请注意串联 L ₁ L ₂中的任何字符串都具有 a ⁿ的形式，因此是 a* 的元素。接下来，取 a* 中的任意字符串；让它成为一个ⁿ。如果 n 是 2 的幂，则它可以由 L _1中的^{n和 L} ₂中的ε的串联形成。否则，n 不是 2 的幂，它可以由来自 L ₁的 ε和来自 L _2的ⁿ的串联形成。因此，L ₁ L ₂ = a*，所以你要证明的定理是错误的。

希望这可以帮助！