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.

Answer 2

I don't remember how to code this in Prolog, but the idea is this:

First rule: If list has only size 3, check if first item is an A and second,third are Bs. If not, return false, else true (size 3 because n >= 1).

Second rule: Check if the first item in the list is an A and the last one is a B. If this is true, recursively use the same code for elements 2 to n-1.

If i understood your problem correctly that should be the perfect Prolog style solution.

Answer 3

Here is my abstruse solution

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

testing:

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

 ?- test.
true.