X和Y由0和1组成且X≠Y的所有字符串X2Y
All the strings X2Y where X and Y are composed of 0s and 1s and X ≠ Y
本题摘自A. Shen的书"Algorithms and Programming. Problems and Solutions"。问题本身是由 M. Sipser 传达的。
作者要求 reader 定义生成以下语言的上下文无关语法：
{X2Y | X ∈ {0, 1}*, Y ∈ {0, 1}*, X ≠ Y}.
首先，我无法理解这样一种语言怎么可能是上下文无关的（从我的新手角度来看）：
X 和 Y 都可以是任何序列，但它们不能同时是一个序列。这对我来说似乎是上下文相关的 属性。
术语 "context-free" 和 "context-sensitive" 背后的真正含义是什么，这与上面的上下文无关语言不矛盾？如何构建这样的语法（我真的很感激提示而不是完整的解决方案）？
既然你要求提示，我就给你一个提示，而不是把整个答案都写出来。这里的困难在于我们需要 X 和 Y 是不同的字符串。我们知道 X2Y 与 X 和 Y 相同不是上下文无关的。这是因为我们有 |X| = |是|要检查的东西——第一个符号匹配，第二个符号匹配，等等。但是，如果 X 和 Y 必须不同，我们只需要保证它们至少在一个地方不同。如果我们可以保证它们的符号编号 N 不同，那么我们就可以保证 X 和 Y 不同。你能写出生成 (0+1)^n 0 (0+1)* 2 (0+1)^n 1 (0+1)* 的上下文无关文法吗？如果是这样，您问题的答案是该 CFG 的语言与交换了不匹配符号的语言的联合（因此 1 先出现，然后是 0）。
本题摘自A. Shen的书"Algorithms and Programming. Problems and Solutions"。问题本身是由 M. Sipser 传达的。
作者要求 reader 定义生成以下语言的上下文无关语法：
{X2Y | X ∈ {0, 1}*, Y ∈ {0, 1}*, X ≠ Y}.
首先，我无法理解这样一种语言怎么可能是上下文无关的（从我的新手角度来看）：
X 和 Y 都可以是任何序列，但它们不能同时是一个序列。这对我来说似乎是上下文相关的 属性。
术语 "context-free" 和 "context-sensitive" 背后的真正含义是什么，这与上面的上下文无关语言不矛盾？如何构建这样的语法（我真的很感激提示而不是完整的解决方案）？
既然你要求提示，我就给你一个提示，而不是把整个答案都写出来。这里的困难在于我们需要 X 和 Y 是不同的字符串。我们知道 X2Y 与 X 和 Y 相同不是上下文无关的。这是因为我们有 |X| = |是|要检查的东西——第一个符号匹配，第二个符号匹配，等等。但是，如果 X 和 Y 必须不同，我们只需要保证它们至少在一个地方不同。如果我们可以保证它们的符号编号 N 不同，那么我们就可以保证 X 和 Y 不同。你能写出生成 (0+1)^n 0 (0+1)* 2 (0+1)^n 1 (0+1)* 的上下文无关文法吗？如果是这样，您问题的答案是该 CFG 的语言与交换了不匹配符号的语言的联合（因此 1 先出现，然后是 0）。