context-free-grammar - ContextFreeGrammar のあいまいさ

Question

CFG が与えられた場合: S--> aS | Sa | b 2 つの異なる pars ツリーから作成できる文字列が見つかりません。

中間状態は再帰を残しましたが、それを排除せずに CFG のあいまいさを示す文字列はありますか? 誰でも助けてくれますか。

Answer 1

ルール 1、2、および 3 を適用すると、次のようになります。

S -> aS -> aSa -> aba

ルール 2、3、1 を適用すると、同じ文字列が得られます。

S -> Sa -> aSa -> aba

あいまいさがあります。

あいまいさをチェックするツールを見つけました: http://services.brics.dk/java/grammar/demo.html

文法を入力してチェックしanalyze the grammar for potential ambiguityます:

S : "a" S
  | S "a"
  | "b"

結果：

*** vertical ambiguity: S[#1] <--> S[#2]
    ambiguous string: "aba"
the grammar is ambiguous!