此题摘自A. Shen的书《算法与编程。问题与解决方案》。这个问题本身是由 M. Sipser 传达的。
作者要求读者定义一个上下文无关语法，生成以下语言:
{X2Y | X ∈ {0, 1}*，Y ∈ {0, 1}*，X ≠ Y}。
首先，我无法理解这样的语言如何能够是上下文无关的(从我的新手角度来看):
X 和 Y 都可以是任意序列，但它们不能同时是一个序列。对我来说，这似乎是一个上下文相关的属性。
“上下文无关”和“上下文敏感”这两个术语背后的真正含义是什么，这与上面的上下文无关的语言并不矛盾？如何构建这样一种语法(我真的很感激一个提示而不是完整的解决方案)？
最佳答案
既然你要求提示，我会给你一个提示，而不是写出整个答案。这里的困难在于我们需要 X 和 Y 是不同的字符串。我们知道 X 和 Y 相同的 X2Y 不是上下文无关的。这是因为我们有 |X| =|Y|要检查的事情 - 第一个符号匹配，第二个符号匹配，等等。但是，如果 X 和 Y 必须不同，我们只需要保证它们至少在一个地方不同。如果我们能保证它们的符号数N不同，那么我们就保证X和Y不同。你能编写一个上下文无关语法来生成 (0+1)^n 0 (0+1)* 2 (0+1)^n 1 (0+1)* 吗？如果是这样，您的问题的答案就是该 CFG 的语言与交换了不匹配符号的语言的并集(因此 1 在前，然后是 0)。
关于grammar - 所有字符串 X2Y，其中 X 和 Y 由 0 和 1 组成，且 X ≠ Y，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59165679/