检查语言是否包含字符串（Prolog）

问题描述：

这是CFG：

S -> T | V
T -> UU
U -> aUb | ab
V -> aVb | aWb
W -> bWa | ba

因此这将接受以下形式：

so this will accept some form of:

{a^n b^n a^m b^m | n,m >= 1} U {a^n b^m a^m b^n | n,m >= 1}

这是我正在使用的代码：

And here is the code I'm working with:

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)),
    !.

截至目前，以下三个字符串返回false：

As of right now, this is returning false for the following three strings:

[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不太满意，因此请自行调试

Any help or insight would be greatly appreciated, I'm not too comfortable with Prolog so debugging this by myself has been a challenge.

答

首先，请注意，这段代码没有意义：

First, note that this code doesn't make sense:

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

在Prolog中有谓词，而不是函数...

In Prolog there are predicates, not functions...

CFG生产规则（非终端）应该吃掉 '包含许多令牌，在Prolog中，这意味着您至少需要两个参数：输入令牌列表，以及在生产成功匹配输入的相关部分之后剩余的内容。

A CFG production rule (a non terminal) should 'eat' a number of tokens, and in Prolog this means you need at least 2 arguments: the input token list, and what remains after a production has successfully matched the relevant part of input.

也就是说，不需要append / 3：只需模式匹配，由统一运算符（=）/ 2

That is, append/3 is not required: just pattern matching, performed by unification operator (=)/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

然后将其命名为：

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

R = [] 表示整个序列已被匹配...

R = [] means the entire sequence has been matched...

检查语言是否包含字符串（Prolog）

相关推荐