Prologue: Recognize a ^ nb ^ (n + 1) language with n> = 1

Question

I understand that I need to find out my homework, but seeing that no one in the class can understand this, I need help.

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

Answer 1

You should use a counter to keep track of what you have found so far. When you find it b, add it to the counter. When you find it a, subtract it. The final value of your counter after going through the whole list should be the same, since you want the number to bbe 1 more than the number a. Here is an example of how to write this 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 it will do almost what you want - it complies with the rules for everyone n >= 0, while you want it for everyone n >= 1. In a typical homework answer, I left this last bit so you can add yourself.

Answer 2

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

Rule 1: If listize is 1, return true if element B.

2: listize 2, false.

3: , A, - B. , 2 -1.

, Prolog.

: . , n = 1 n = 2. .

Answer 3

Here is my smart decision

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