轉換成明確的語法從二義性文法

我已經模糊的上下文無關文法具有產品：轉換成明確的語法從二義性文法

s --> [0],s,[1]. 
s --> [0],s. 
s --> [].

這是當然的曖昧，因爲我00011可以得出兩個人解析樹。我必須寫下我的文法，它是明確的語法並描述相同的語言。我的想法是：

s --> [0],s,[1]. 
    s --> [0],a. 
    s --> []. 
    a --> [0],a. 
    a --> [].

這很好嗎？我怎麼能證明這一點？

來源

2014-04-07 Vous

0和1是我們的字母表。 []表示空集，用於Prolog。當我們在序言中 - > [0]，s，[1]時，我們寫S - > 0S1。 – Vous

你明白你的語法是什麼語言嗎？如果你需要簡短的回答，那麼是的，你已經解決了歧義，第二種形式是明確的語法。 –

這是可以由此規則生成的字母表{1,0}下的單詞：S-> 0 S 1 ...？ – Vous

所以你怎麼能證明歧義？在Prolog，這是容易實現混凝土的句子：

| ?- length(Xs,N), bagof(t,phrase(s,Xs),[_,_|_]).    

N = 3 
Xs = [0,0,1] ? ; 

N = 4 
Xs = [0,0,0,1] ? ; 

N = 5 
Xs = [0,0,0,0,1] ? ; 

N = 5 
Xs = [0,0,0,1,1] ? ; 

N = 6 
Xs = [0,0,0,0,0,1] ?

這證明是混凝土長度不確定性，並給出了相關的反例。

有，但只有經過一段時間後可能顯示一個警告：bagof/3具有存儲整套解決方案的莫名其妙。所以如果這個設置非常大，bagof/3可能會溢出。以下查詢以獲得冗餘解決方案的代價避免了此錯誤：

| ?- length(Xs,N), phrase(s,Xs), bagof(t,phrase(s,Xs),[_,_|_]). 

N = 3 
Xs = [0,0,1] ? ; 

N = 3 
Xs = [0,0,1] ? ; 

N = 4 
Xs = [0,0,0,1] ? ; 

N = 4 
Xs = [0,0,0,1] ? ; 

N = 4 
Xs = [0,0,0,1] ? ; 

N = 5 
Xs = [0,0,0,1,1] ...

隨着您的改進語法，查詢循環。這意味着系統無法找到反例。至少不是1000以下的長度，這是我測試的。

約在序言寫DCG中一些一般性意見：

嘗試最後把遞歸的情況下，這可能會節省一些空間。
您可能需要使用雙引號字符串來表示終端。有關更多信息，請參閱this answer。

來源

2014-06-17 11:18:43 false

轉換成明確的語法從二義性文法

回答

相關問題