は（プロローグ）これはCFGです

Question

チェック作業：今のよう

in_lang([]). 
in_lang(L) :- 
    mapS(L), !. 

mapS(L) :- 
    mapT(L) ; mapV(L),!. 

mapT(L) :- 
    append(L1, mapU(L), L), mapU(L1), !. 

mapU([a|T]) :- 
    ((append(L1,[b],T), mapU(L1)) ; (T = b)),!. 

mapV([a|T]) :- 
    ((append(L1,[b],T), mapV(L1)) ; 
    (append(L1,[b],T), mapW(L1))), 
    !. 

mapW([b|T]) :- 
    ((append(L1,[a],T), mapW(L1)) ; 
    (T = a)), 
    !. 

、これは以下の3つの文字列のためにfalseを返すされています

[a,a,b,b,a,b] // this should be true 
[a,a,a,b,b,a,a,b,b,b] // this should be true as well 
[a,a,a,b,b,a,b,b,b] // this one IS false 

私はPrologに慣れていないので、自分でこれをデバッグすることは難しい課題でした。

Answer 1

まず、このコードは意味がありませんのでご注意：

... append(L1, mapU(L), L) ... 

プロローグでは述語、ない機能がある...

A CFGの生成規則（非ターミナル）いくつかのトークンを「食べる」必要があります.Prologでは、入力トークンリストと、プロダクションが入力の関連部分にうまく一致した後に残るものが少なくとも2つ必要です。次いで統一オペレータによって実行されるだけでパターンマッチング、（=）/ 2

mapS(L1, L) :- mapT(L1,L) ; mapV(L1,L). 
mapT(L1, L) :- mapU(L1,L2), mapU(L2,L). 
mapU(L1, L) :- L1=[a|L2], mapU(L2,L3), L3=[b|L] ; L1=[a,b|L]. 
... complete the translation 

とそれを呼び出す：/ 3を追加しているが必要とされない

?- mapS([a,a,b,b,a,b],R). 
R = [] ; 
false. 

R = []全体を意味シーケンスは一致しました...

Answer 2

mapTの定義では、appendの引数に「戻り値」のmapUを使用しようとしています。しかし、mapUは述部であり、述部には戻り値がありません。

代わりに、通常は、述語が目的の「戻り値」にバインドするバインドされていない変数を持つ述語を書き込みます。 predciateが証明された後、今バインドされた変数は後続の述語で使用できます。

Answer 3

dcg！そしてlibrary(double_quotes)。

:- set_prolog_flag(double_quotes, chars). 

s --> t | v. 
t --> u, u. 
u --> "a",u,"b" | "ab". 
v --> "a",v,"b" | "a",w,"b". 
w --> "b",w,"a" | "ba". 

| ?- use_module(library(double_quotes)). 

| ?- length(L,N), phrase(s, L). 
L = "abab", N = 4 ? ; 
L = "abab", N = 4 ? ; 
L = "aabbab", N = 6 ? ; 
L = "abaabb", N = 6 ? ; 
L = "aababb", N = 6 ? ; 
L = "abbaab", N = 6 ? ; 
L = "aaabbbab", N = 8 ? ; 
L = "aabbaabb", N = 8 ? ; 
L = "abaaabbb", N = 8 ? ; 
L = "aaababbb", N = 8 ? ...