常规语言和连接

Question

常规语言在串联下是封闭的 - 这可以通过将一种语言的接受状态与 epsilon 转换为下一种语言的开始状态来证明。

如果我们考虑语言 L = {a^n | n >=0}，这种语言是正则的（它只是一个*）。如果我们将它与另一种语言连接起来 L = {b^n | n >=0}，这也是正则，我们最终得到a^nb^n，但我们显然知道这不是正则。

我的逻辑哪里出了问题？

Answer 1

两种语言 L ₁和 L ₂的连接的定义是所有字符串 wx 的集合，其中 w ∈ L ₁和 x ∈ L ₂。这意味着 L ₁ L ₂由将来自 L _{1 的}一个字符串和来自 L _{2 的}一个字符串配对形成的所有可能的字符串组成，这不一定与配对来自每种语言的匹配字符串相同。

结果，正如@Oli Charlesworth 指出的那样，你在这里得到的语言实际上并不是 { a ⁿ b ⁿ | n 在 N }。相反，它是语言 { a ⁿ b ^m | n in N and m in N }，即语言 a*b*。这种语言是常规的，因为它是由常规语言给出的。

希望这可以帮助！