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