context-free-grammar - 寻找更复杂语言的上下文无关语法的方法

Question

我在处理以下问题时遇到问题。

给出以下语言的上下文无关文法：

{x#y | x,y in {0,1}* and |x| != |y|} 

解决这个问题的最佳方法是什么？目前我只是用直觉来解决这些问题，但有没有有用的技术？即你能想到这种语言的 PDA 会是什么样子，然后从中推导出语法吗？有没有使用语法 A 和 B 找到语法 G = A 和 B 的方法？

我正在努力寻找如何解决这个问题，所以任何帮助都将不胜感激。

谢谢。

Answer 1

使用直觉是一项有价值的技术。当您解决更多此类问题时，您的直觉会变得更加敏锐，因此变得更容易。

没有将语言描述转换为 CFG 的正式技术（除非描述是映射到 CFG 上的东西，当然，就像一组生产规则）。通常，无法确定一种语言是否是上下文无关的（尽管 CFG 必须符合许多约束，因此通常可以证明一种语言不是CFG，甚至可以半机械地使用计数参数。）并且甚至两种上下文无关语言的交集不一定是上下文无关的，因此没有程序可以采用两种上下文无关语言并为它们的连接生成 CFG。

但是，两种上下文无关语言的联合是上下文无关的，并且可以从两种语言的 CFG 中机械地生成 CFG。因此，有可能将问题分解为多个部分。

对于这个特定问题，我建议使用简单的启发式方法，它通常适用于您在正式语言课程中遇到的那种问题：尝试将问题建立在您知道答案的简单问题上。

如上所述，两个 CFL 的并集是上下文无关的。串联也是如此，定义为：

L ₁ · L ₂ = { xy | x ∈ L ₁ ∧ y ∈ L ₂ }

这里有两种方法，都基于能够构造相似的语言 where | x | = | 是|。任何字符串，其中 | x | ≠ | 是| 右侧或左侧必须有更多字符。根据您的喜好，您可以在中间（在分隔符的一侧或另一侧）或一端添加这些额外的字符。这两种方法都涉及使用联合；其中一个是连接，另一个是嵌入。

祝你好运。