如何编写对列表执行某些操作的序言程序

Question

我想编制一个仅使用字符 {a, b} 的列表。

我的 objective 是 Prolog returns 仅当用户输入的列表包含 n 个 a 或至少一个 a 但必须仅以一个 b 结束时才为真，仅此而已不少于一个 b.

示例：aaab 正确，aba 错误，b 错误，a 错误。

这是我的代码：

langage([]).
langage([a | S]):-
    langage(S).

这里的问题是只接受a的n个数，并没有以b结束。但我希望它以字母 b.

结尾

希望有人能帮助我。

Answer 1

使用 Prolog 的 dcg-notation:

:- set_prolog_flag(double_quotes, chars).
:- use_module().   % SWI, SICStus only

monlangage --> "ab" | "a", monlangage.

?- phrase(monlangage,L).
   L = "ab"
;  L = "aab"
;  L = "aaab"
;  L = "aaaab"
;  L = "aaaaab"
;  ...

请参阅 如何获得如此简洁的答案（Scryer 和 Trealla 中的默认答案）。否则，您会得到 L = [a,a,a,b] 等答案

为了练习定从句语法，将语法重新表述几次会有所帮助。比如有一些冗余需要识别：

monlangage --> "ab" | "a", monlangage.
%               ^      ^

两种选择都以 "a"!

开头

monlangage_bis --> "a", ( "b" | monlangage_bis ).

?- phrase(monlangage_bis,L).
   L = "ab"
;  L = "aab"
;  L = "aaab"
;  L = "aaaab"
;  L = "aaaaab"
;  ...

现在，这些语言真的一样吗？以上查询是否足以确保这一点？好好考虑

sonlangage --> "ab" | "a", sonlangage | "b".    % règle provocateur !

?- phrase(sonlangage,L).
   L = "ab"
;  L = "aab"
;  L = "aaab"
;  L = "aaaab"
;  L = "aaaaab"
;  ...

看起来几乎一样，但是

?- phrase(monlangage, "b").
false.
?- phrase(sonlangage, "b").
   true.     % unexpected

我们如何快速识别这些差异？如上所述检查解决方案集没有帮助。背后的真正问题是 Prolog 以 不公平 的方式列举了解决方案。

我们能做的就是按长度枚举所有solutions/answers。

?- length(L,_), phrase(monlangage, L).
   L = "ab"
;  L = "aab"
;  L = "aaab"
;  L = "aaaab"
;  ...
?- length(L,_), phrase(sonlangage, L).
   L = "b"      % caught!
;  L = "ab"
;  L = "ab"     % redundant (but not incorrect)
;  L = "aab"
;  L = "aab"    % idem
;  ...

这不会找出所有错误，但至少我们可以确保在一定的有限长度内没有差异。

另一种重新表述 monlangage//0 的方法是更好地概述所有句子都以“b”结尾。

monlangage_ter --> "a", as, "b".

as --> "" | "a", as.

或者更通用的方式：

monlangage_quater --> "a", star("a"), "b".

star(NT__0) --> "" | NT__0, star(NT__0).

Answer 2

你可以这样写：

langage([a,b]).
langage([a | S]):-
    langage(S).

因此您的列表需要在 a 和 b 结束，任何领先的 a 都将被第二条规则删除。使用 SWISH 测试：

?- langage([a,a,a,b]).
true;
false.

?- langage([a,b,a]).
false.

?- langage([a]).
false.

?- langage([b]).
false.

---

但是，如果您想要一个以 a 开头且 n>=1 跟进 b 的列表，试试这个（未测试）：

langageB([b]).
langageB([b| S]):-
    langageB(S).

langage([a| S]):-
    langageB(S).