文法があいまいであるかどうかを証明するにはどうすればよいですか？

Question

私たちが文法を持っていれば、これが曖昧ではないことを正しく証明するにはどうすればよいのですか？私の意見では、それを記述するのは難しいのですが、そのための数学的または論理的証拠はありますか？

そして、L（G）= G？私が論理的な証明を与えるのが難しい次のこと。

誰かがお手伝いします。

Answer 1

確定的なパーサーを作成することによって、文法が明白であることを証明できます。 2つの異なる解析木を持つ文を見つけることによって、あいまいであることを証明することができます（または、言い換えれば、2つの異なる左辺または右辺の導関数を使用して）。

文法のあいまいさが判明しないため、そのような証明を生成するための決定的なアルゴリズムはありません。

---

は、私はあなたがL(G) = Gことを証明することによって何を意味するのか見当がつかない。 L(G)は文字列のセットであり、Gは文法であるため、これは明らかに真実ではありません。 2つのオブジェクトは異なる宇宙からのものなので、同じではありません。おそらく、文字列の一部がSと等しいことを証明することを意味するのは、L(G)ですか？繰り返しますが、この問題は一般的には決めることはできませんが、多くの有益な場合にはそのような証明を構成することができます。一般的な戦略は、文字列の長さに誘導を使用することです。