grammar - 一种语言和证明 它是如何模棱两可的？

Question

我刚参加了期中考试，但无法回答这个问题。

我们如何才能表明下面的语言是模棱两可的？

L={a ⁿ b ^m c ^p : n≠m} U {a ⁿ b ^m c ^p : m≠p}

我认为这很难，谁能帮助我使用自动化工具或......我们如何证明它？

Answer 1

考虑一种可能的语言语法：{anbmcp : n≠m}

S → A X C | X B C
X → ε | a X b
A → a | a A
B → b | B b
C → ε | C c

在这个语法中，任何单词的最左边的派生都不会扩展，C直到所有其他非终结符都被扩展。对于联合的另一半，一个非常相似的语法 (将在扩展任何其他非终结符之前类似地扩展所有s 。因此，两个子集的交集中的任何单词都将具有（至少）两个不同的派生。anbmcp : m≠p}A

证明该语言本质上是模棱两可的，需要证明上述对于该语言的任何语法都是正确的。这样的证明有效地基于 Ogden 引理，它是上下文无关语言的泵引理的推广；证明包括证明可以以两种不同的方式“抽取”某个词。

比较容易找到相似语言 本质上是模棱两可的证据：它经常被用作形式语言理论教科书中的示例。我认为您的语言的证明“更难”，因为它可能需要考虑更多案例，但应该非常相似。{anbmcp : n=m} ∪ {anbmcp : m=p}

另一种方法是 Flajolet 的分析方法。