prolog - Prolog：识别 n >= 1 的 a^nb^(n+1) 语言

Question

我知道我需要弄清楚自己的作业，但是看到班上没有人能弄清楚，我需要一些帮助。

编写一个 Prolog 程序，p(X) 如果X是一个由n a' 后跟n+1 b's 组成的列表，则为真，对于任何n >= 1。

Answer 1

我不记得如何在 Prolog 中编写代码，但想法是这样的：

规则 1：如果 listsize 为 1，如果元素是 B，则返回 true。

规则 2：如果 listsize 为 2，则返回 false。

规则 3：检查列表中的第一项是否为 A，最后一项是否为 B。如果为真，则将元素 2 的解决方案返回到 listsize-1。

如果我正确理解了您的问题，那应该是完美的 Prolog 风格解决方案。

编辑：我完全忘记了这一点。我编辑了答案以考虑 n = 1 和 n = 2 的情况。感谢 Heath Hunnicutt。

Answer 2

您应该使用计数器来跟踪您到目前为止发现的内容。当您找到 时b，将 1 添加到计数器中。当你找到 aa时，减去一个。遍历整个列表后计数器的最终值应该是 1，因为您希望b's 的数量比a's 的数量多 1。这是一个如何在代码中编写它的示例：

% When we see an "a" at the head of a list, we decrement the counter.
validList([a|Tail], Counter) :-
  NewCounter is Counter - 1,
  validList(Tail, NewCounter).

% When we see an "b" at the head of a list, we increment the counter.
validList([b|Tail], Counter) :-
  NewCounter is Counter + 1,
  validList(Tail, NewCounter).

% When we have been through the whole list, the counter should be 1.
validList([], 1).

% Shortcut for calling the function with a single parameter.
p(X) :-
  validList(X, 0).

现在，这几乎可以满足您的要求 - 它符合 all 的规则n >= 0，而您希望它适用于 all n >= 1。在典型的家庭作业回答方式中，我把最后一点留给你自己补充。

Answer 3

这是我的深奥解决方案

:-use_module(library(clpfd)).

n(L, N) -->
    [L],
    {N1 #= N-1
    },
    !, n(L, N1).
n(_, 0) --> [], !.

ab -->
    n(a, N),
    {N1 is N + 1
    },
    n(b, N1).

p(X) :- phrase(ab, X).

test :-
    p([b]),
    p([a,b,b]),
    p([a,a,b,b,b]),
    p([a,a,a,b,b,b,b]),
    \+ p([a]),
    \+ p([a,b]),
    \+ p([a,a,b,b]),
    \+ p([a,b,b,c]).

测试：

 ?- [ab].
% ab compiled 0.00 sec, -36 bytes
true.

 ?- test.
true.