是L = {a ^ mb ^ nc ^ k |如果（m = n）则（n = k）}还是CFL？

Question

我看到用这种语言，到我们决定m = n时；那么我们就没有b了；所以我们不能用c来修饰它们。所以，我认为它不应该是CFL。

但是下面的解决方案表明它是CFL

在上述给定的解决方案中，L2 CFL是否正确？

Answer 1

语言L = {a ^ m b ^ n c ^ k | if（m = n）则（n = k）}正是上下文无关的语言，正是出于第二种推导中给出的原因：if（m = n）then（n = k）的条件不仅在m = n和n = k，但是当m不等于n时也是如此。如果条件是（m = n）和（n = k），则该语言将不是上下文无关的，因为该条件将等效于m = n = k。

我们可以通过在L2中显示L中的任何内容来证明该语言在上下文无关的情况下的推导，反之亦然。

假设字符串w在我们的语言L中。那么m = n或不是。如果m = n，则n = k。但是字符串w在L2中，因为L2是两种语言的并集，其中一种包含所有n = k的字符串。如果不是m = n，则字符串w在L2中，因为L2是两种语言的并集，另一种是m和n不相等的所有字符串的语言。因此，L中的任何字符串都在L2中。

假设字符串w在L2中。那么m = n为假，或者n = k为真。假设m = n为假。那么如果（m = n）则（n = k）的条件是空虚的（因为假设是错误的，并且一切都源自矛盾）。如果n = k为真，则无论假设的真值如何，（假设）那么（n = k）的蕴涵都必须为真。因此，L2中的任何字符串都在L中。

因为L和L2是彼此的子集，所以它们必须相等。