我在处理以下问题时遇到问题。
给出以下语言的上下文无关语法：
{x#y | x,y in {0,1}* and |x| != |y|}
解决这个问题的最佳方法是什么？目前，我只是用直觉来解决类似这样的问题，但是有没有有用的技术？也就是说，您能想到这种语言的PDA的外观，然后从中得出语法吗？是否有使用语法A和B查找语法G = A和B的方法？
我正在努力寻找解决方法，因此我们将不胜感激。
谢谢。
使用直觉是一种有价值的技术。当您解决更多此类问题时，您的直觉会越来越清晰，因此变得更容易。
没有将语言描述转换为CFG的正式技术（当然，除非描述是映射到CFG的东西，就像一组生产规则一样）。通常，无法确定语言是否是上下文无关的（尽管CFG必须符合很多约束，所以通常可以证明语言不是CFG，即使是半机械地使用计数参数也是如此）。两种上下文无关的语言的交集甚至不一定是上下文无关的，因此没有一种过程可以采用两种上下文无关的语言并为它们的结合生成CFG。
但是，两种上下文无关语言的联合是上下文无关的，并且CFG可以从两种语言的CFG中自动生成。因此，有可能将问题分解为多个部分。
对于这个特定问题，我建议使用一种简单的启发式方法，该方法通常可以解决您在形式语言课程中遇到的那种问题：尝试将问题建立在您知道答案的更简单问题上。
如上所述，两个CFL的并集是上下文无关的。串联也定义为：
L 1 · L 2 = { xy | X ∈大号1 ∧ ý ∈大号2 }
这是两种方法，两种方法都基于能够构造类似的语言，其中| x | = | y |。任何字符串，其中| x | ≠| y | 右侧或左侧必须有更多字符。根据您的倾向，您可以在中间（分隔符的一侧或另一侧）或两端之一添加这些额外的字符。这两种方法都涉及使用工会。其中一个是串联，另一个是嵌入。
祝你好运。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句