Prolog程序識別上下文無關文法一^ N b^N

Question

使用序言我想寫一個謂詞識別上下文無關文法如果輸入列表匹配的CFG返回true。
輸入的字母只包含a,b。 我試圖匹配的CFG是

S-> TT 
T -> aTb | ab 

我不太清楚如何實現這一點，主要的T規則。

s(S0,S):-t(S0,S),t(S1,S). 
t(S0,S):-S0 = a, t(S1,S), S1 = b; S0 = a, S1 = b. 

match([H|T] :- s(H,T). 

所以，如果我查詢[a, a, b, b]它應該返回true。 但是，我只是得到一個無限循環。 我不太清楚如何執行a^n b^n規則。

Answer 1

我會寫的CFG這樣：

S -> T 
T -> a T b | {epsilon} 

直接轉化爲一個DCG：

s --> t. 
t --> []. 
t --> a, t, b. 

注意我換了小量的規則，去產生短語的能力。

翻譯即DCG手工：

s(S0,S) :- t(S0,S). 
t(S0,S0). 
t(S0,S) :- S0=[a|S1], t(S1,S2), S2=[b|S]. 

產量

?- phrase(s,L). 
L = [] ; 
L = [a, b] ; 
L = [a, a, b, b] ; 
L = [a, a, a, b, b, b] ; 
...