Automata-theory-ambiguity-in-grammar

文脈自由文法のあいまいさ

文脈自由文法 G が何らかの文字列* w∈L（G）*に対して複数の派生ツリーを持つ場合、それは*曖昧な文法*と呼ばれます。 その文法から生成された文字列には、右端または左端の派生が複数存在します。

問題

文法Gがプロダクションルールであるかどうかを確認します-

X→X + X | X *X | X | a

あいまいであるかどうか。

溶液

文字列「a + a* a」の派生ツリーを見つけましょう。 左端に2つの派生があります。

導出1 *-X→X + X→a + X→a + X *X→a + a X→a + a * a

• 解析ツリー1 *-

解析ツリー1

導出2 *-X→X *X→X + X X→a + X X→a + a X→a + a * a

• 解析ツリー2 *-

解析ツリー2

1つの文字列「a + a * a」に対して2つの解析ツリーがあるため、文法 G はあいまいです。