Prolog: Recognize a^n b^(n+1) language for n >= 1

Question

I understand that I need to figure out my own homework, but seeing that noone in the class can figure it out, I need some help.

Write a Prolog program such that p(X) is true if X is a list consisting of n a's followed by n+1 b's, for any n >= 1.

Answer 1

You should use a counter to keep track of what you have found so far. When you find an b, add one to the counter. When you find a a, subtract one. The final value of your counter after the whole list is traversed should be one, since you want the number of b's to be 1 more than the number of a's. Here's an example of how to write that in code:

% 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).

Now, this will do almost what you want - it matches the rules for all n >= 0, while you want it for all n >= 1. In typical homework answer fashion, I've left that last bit for you to add yourself.