Пролог: распознать язык a^n b^(n+1) для n ›= 1

Вы должны использовать счетчик, чтобы отслеживать, что вы уже нашли. Когда вы найдете b, добавьте один к счетчику. Когда вы найдете a, вычтите один. Окончательное значение вашего счетчика после обхода всего списка должно быть 1, так как вы хотите, чтобы количество b было на 1 больше, чем количество a. Вот пример того, как написать это в коде:

% 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. В типичной манере ответов на домашнее задание я оставил этот последний фрагмент для вас, чтобы вы могли добавить его сами.

Я не помню, как это закодировать на Прологе, но идея такова:

Правило 1: Если listsize равен 1, вернуть true, если элемент является B.

Правило 2: Если размер списка равен 2, вернуть false.

Правило 3: проверьте, является ли первый элемент в списке A, а последний — B. Если это так, верните решение для элементов 2 в listsize-1.

Если я правильно понял вашу проблему, это должно быть идеальным решением в стиле Prolog.

Редактировать: я совсем забыл об этом. Я отредактировал ответ, чтобы рассмотреть случай n = 1 и n = 2. Спасибо Хиту Ханникатту.

Вот мое заумное решение

:-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.