我遇到以下问题时遇到问题 .
为以下语言提供上下文无关语法：
{x#y | x,y in {0,1}* and |x| != |y|}
处理这个问题的最佳方法是什么？目前我只是用直觉来解决这些问题，但有没有有用的技巧？也许你能想到这种语言的PDA会是什么样的，然后从中得出语法吗？有没有使用语法A和B找到语法G = A和B的方法？
我很难看到如何解决这个问题，所以任何帮助都会非常感激 .
谢谢 .
使用直觉是一种有 Value 的技术 . 当你解决更多这样的问题时，你的直觉会变得更加敏锐，因此它会变得更容易 .
没有正式的技术可以将语言描述转换为CFG（除非描述是映射到CFG的东西，当然，就像一组 生产环境 规则） . 一般来说，语言是否无上下文是可判定的（尽管CFG必须符合许多约束，因此通常可以证明语言不是CFG，甚至是半机械地使用计数参数 . ）甚至不一定是两个无上下文语言的交集是无上下文的情况，因此没有可以采用两种无上下文语言并为它们的连接生成CFG的过程 .
但是，两种无上下文语言的联合是无上下文的，CFG可以通过两种语言的CFG机械地生成 . 因此有可能将问题分解成碎片 .
在这个特殊问题的情况下，我建议一个简单的启发式方法，它通常适用于您在正式语言课程中遇到的那类问题：尝试将问题基于您知道答案的简单问题 .
如上所述，两个CFL的并集是无上下文的 . 串联也是如此，定义为：
L1·L2 = {xy | x∈L1∧y∈L2}
这里有两种方法，都基于能够在| x |中构建类似的语言= | y | . 任何字符串，其中| x | ≠| y |必须在右侧或左侧有更多字符 . 根据您的倾向，您可以在中间（分隔符的一侧或另一侧）或其中一端添加这些额外字符 . 这两种方法都涉及使用联合;其中一个是串联，另一个是嵌入 .
祝好运 .
1 回答
使用直觉是一种有 Value 的技术 . 当你解决更多这样的问题时，你的直觉会变得更加敏锐，因此它会变得更容易 .
没有正式的技术可以将语言描述转换为CFG（除非描述是映射到CFG的东西，当然，就像一组 生产环境 规则） . 一般来说，语言是否无上下文是可判定的（尽管CFG必须符合许多约束，因此通常可以证明语言不是CFG，甚至是半机械地使用计数参数 . ）甚至不一定是两个无上下文语言的交集是无上下文的情况，因此没有可以采用两种无上下文语言并为它们的连接生成CFG的过程 .
但是，两种无上下文语言的联合是无上下文的，CFG可以通过两种语言的CFG机械地生成 . 因此有可能将问题分解成碎片 .
在这个特殊问题的情况下，我建议一个简单的启发式方法，它通常适用于您在正式语言课程中遇到的那类问题：尝试将问题基于您知道答案的简单问题 .
如上所述，两个CFL的并集是无上下文的 . 串联也是如此，定义为：
L1·L2 = {xy | x∈L1∧y∈L2}
这里有两种方法，都基于能够在| x |中构建类似的语言= | y | . 任何字符串，其中| x | ≠| y |必须在右侧或左侧有更多字符 . 根据您的倾向，您可以在中间（分隔符的一侧或另一侧）或其中一端添加这些额外字符 . 这两种方法都涉及使用联合;其中一个是串联，另一个是嵌入 .
祝好运 .