我怎麼能證明這個語法是不明確的？

S -> bA|aB 
A -> a|aS|bAA 
B -> b|bS|aBB

任何簡單的方法，而不是試圖找到一個字符串，會產生兩個分析樹？我怎麼能證明這個語法是不明確的？

有人可以給我一個可以證明這一點的字符串。

來源

2011-02-02 crowso

對我來說這看起來像它明確。 – crowso 2011-02-02 18:53:02

請允許我歡迎您來到StackOverflow，並提醒我們通常在這裏做的三件事：1）當您獲得幫助時，嘗試給予它**在您的專業領域回答問題** 2）[閱讀常見問題] http://tinyurl.com/2vycnvr）3）當你看到很好的問答時，把它們投票[`使用灰色三角形]（http://i.imgur.com/kygEP.png），作爲系統基於用戶通過分享知識獲得的聲譽。還記得接受更好地解決你的問題的答案，如果有的話，['通過按複選標記]（http://i.imgur.com/uqJeW.png） – 2011-02-02 18:56:16

有沒有簡單的方法來證明上下文無關語法模糊 - 實際上， the question is undecidable，通過減少到Post correspondence problem。

來源

2011-02-02 18:56:52

是的，但我不能在答題紙上寫下。我應該看看哪些語法屬性來正確選擇產生2個解析樹的字符串？ – crowso 2011-02-03 03:47:54

有一個字符串，但：bbaaba

S -> bA -> bbAA -> bbaA -> bbaaS -> bbaabA -> bbaaba 
S -> bA -> bbAA -> bbaSA -> bbaaBA -> bbaabA -> bbaaba

來源

2013-03-24 22:08:05 Shweta

我怎麼能證明這個語法是不明確的？

回答

相關問題