此问题摘自A. Shen的书“算法与编程。问题与解决方案”。问题本身由M. Sipser传达。
作者请读者定义一种上下文无关的语法，该语法生成以下语言：
{X2Y | X ∈ {0, 1}*, Y ∈ {0, 1}*, X ≠ Y}。
首先，我不明白这种语言如何与上下文无关（从我的新手角度来看）：X和Y都可以是任何序列，但不能同时是一个序列。在我看来，这似乎是上下文相关的属性。术语“无上下文”和“上下文敏感”背后的真正含义是什么，与上面的无上下文语言没有矛盾？如何构造这样的语法（我会很感激提示而不是完整的解决方案）？
由于您要求提供提示，我会给您一个提示，而不是将整个答案都写出来。这里的困难是我们需要X和Y是不同的字符串。我们知道X2Y与X和Y相同并非不是上下文无关的。这是因为我们有| X |。 = | Y |要检查的内容-第一个符号匹配，第二个符号匹配，依此类推。但是，如果X和Y必须不同，我们只需要保证它们至少相差一个即可。如果我们可以保证它们的符号编号N不同，那么我们可以保证X和Y不同。您可以编写一个上下文无关的语法来生成（0 + 1）^ n 0（0 + 1）* 2（0 + 1）^ n 1（0 + 1）*吗？如果是这样，那么您的问题的答案就是CFG的语言与交换了不匹配符号的语言的结合（所以先出现1，然后是0）。