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

Question

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

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

Answer 1

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

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

规则 2：
如果列表大小为 2，则返回 false。

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

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

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

Answer 2

您应该使用计数器来跟踪到目前为止您发现的内容。当您找到 b 时，将计数器加一。当找到 a 时，减一。遍历整个列表后计数器的最终值应该为 1，因为您希望 b 的数量比 a 的数量多 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).

现在，这几乎可以满足您的要求 - 它匹配所有 n >= 0 的规则，而您想要的对于所有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.