如果一种正则语言只包含Kleene星形，那么它是否有可能来自两种非正则语言的连接

Question

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

谢谢。

Answer 1

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

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

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

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

但是，我要声称L₁L₂ = a*。首先，请注意，串联 L₁L₂ 中的任何字符串的形式为ⁿ n，因此是 a* 的元素。接下来，取 a* 中的任何字符串;让它成为一个ⁿ。如果 n 是 2 的幂，那么它可以形成为 L₁ 的 n 和 L₂ 的^ε 的串联。否则，n 不是 2 的幂，它可以形成为 L₁ 的 ε 和 L₂ 的ⁿ 的串联。因此，L₁L₂ = a*，所以你试图证明的定理是假的。

希望这有帮助！