ContextFreeGrammar歧義

Question

給出一個CFG：S--> aS | Sa | b我無法找到任何可以從兩個不同的樹形成的字符串。

中間狀態已經離開遞歸，但沒有消除，是否有任何顯示CFG歧義的字符串？任何人都可以幫助PLZ。

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!