grammar - 1 つの言語と証明 どのように曖昧なのか?

Question

中間試験を受けたばかりですが、この質問に答えることができませんでした。

次の言語があいまいであることをどのように示すことができますか?

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

これは非常に難しいと思います。誰が自動化ツールを手伝ってくれますか...それをどのように証明できますか?

Answer 1

言語の可能な文法を 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 を展開します。したがって、2 つのサブセットの共通部分にある単語には、(少なくとも) 2 つの異なる派生語があります。anbmcp : m≠p}A

言語が本質的にあいまいであることを証明するには、上記がその言語の文法に当てはまることを証明する必要があります。このような証明は、文脈自由言語のポンピング補題の一般化である Ogden の補題に効果的に基づいています。証明は、いくつかの単語が 2 つの異なる方法で「ポンピング」できることを示すことで構成されます。

同様の言語が本質的に曖昧であることの証明を見つけるのは比較的簡単 です。形式言語理論の教科書でよく例として使用されます。おそらくより多くのケースを考慮する必要があるという点で、あなたの言語の証明は「より難しい」と思いますが、かなり似ているはずです。{anbmcp : n=m} ∪ {anbmcp : m=p}

別のアプローチは、Flajolet の分析法です。