concatenation - 常规语言和串联

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₁ 中的一个字符串和 L_{2 中的一个字符串配对形成的所有可能字符串组成}，这不一定与配对来自每种语言的匹配字符串相同。

因此，正如@Oli Charlesworth 指出的那样，您返回此处的语言实际上并不是 { aⁿbⁿ | N 中的 n}。相反，它是语言 { aⁿb^m | n in N 和 m in N }，即语言 a*b*。这种语言是常规语言，因为它是由常规语言给出的。

希望这对您有所帮助!