How to code a prolog program that does some operations on list

Question

I want to program a list that uses only the characters {a, b}.

My objective is that Prolog returns true only if the list that the user enter contains n number of a, or at least one a but has to finish with one b only, no more and no less than just one b.

Example: aaab is correct, aba is incorrect, b is incorrect, a is incorrect.

Here's my code :

langage([]).
langage([a | S]):-
    langage(S).

The problem here is that it only accepts n numbers of a, and does not finish with b. But I want it to finish with the letter b.

I hope someone can help me.

Answer 1

You could write it like this:

langage([a,b]).
langage([a | S]):-
    langage(S).

So your list needs to end on a and b, any leading a's will be stripped by the second rule. Tested with SWISH:

?- langage([a,a,a,b]).
true;
false.

?- langage([a,b,a]).
false.

?- langage([a]).
false.

?- langage([b]).
false.

---

However, if you wanted to have a list starting with a with n>=1 follow up b, try this (not tested):

langageB([b]).
langageB([b| S]):-
    langageB(S).

langage([a| S]):-
    langageB(S).

Answer 2

Using Prolog's dcg-notation:

:- set_prolog_flag(double_quotes, chars).
:- use_module(library(double_quotes)).   % SWI, SICStus only

monlangage --> "ab" | "a", monlangage.

?- phrase(monlangage,L).
   L = "ab"
;  L = "aab"
;  L = "aaab"
;  L = "aaaab"
;  L = "aaaaab"
;  ... .

See this how to get such compact answers (default in Scryer and Trealla). Otherwise, you get answers like L = [a,a,a,b] etc.

To get some practice with Definite Clause Grammars it helps to reformulate the grammar a couple of times. For example, there is some redundancy to be identified:

monlangage --> "ab" | "a", monlangage.
%               ^      ^

Both alternatives start with "a"!

monlangage_bis --> "a", ( "b" | monlangage_bis ).

?- phrase(monlangage_bis,L).
   L = "ab"
;  L = "aab"
;  L = "aaab"
;  L = "aaaab"
;  L = "aaaaab"
;  ... .

Now, are these languages really the same? Is above query sufficient to ensure this? Well consider

sonlangage --> "ab" | "a", sonlangage | "b".    % règle provocateur !

?- phrase(sonlangage,L).
   L = "ab"
;  L = "aab"
;  L = "aaab"
;  L = "aaaab"
;  L = "aaaaab"
;  ... .

Looks pretty much the same, yet,

?- phrase(monlangage, "b").
   false.
?- phrase(sonlangage, "b").
   true.     % unexpected

How can we identify such differences quickly? Inspecting the set of solutions as above did not help. The real problem behind was that Prolog enumerated the solutions in an unfair manner.

What we can do is to enumerate all solutions/answers by length.

?- length(L,_), phrase(monlangage, L).
   L = "ab"
;  L = "aab"
;  L = "aaab"
;  L = "aaaab"
;  ... .
?- length(L,_), phrase(sonlangage, L).
   L = "b"      % caught!
;  L = "ab"
;  L = "ab"     % redundant (but not incorrect)
;  L = "aab"
;  L = "aab"    % idem
;  ... .

This will not find all the errors, but at least we can ensure that there are no differences up to a certain finite length.

Another way to reformulate monlangage//0 would be to better outline that all sentences end with "b".

monlangage_ter --> "a", as, "b".

as --> "" | "a", as.

Or in a more generic fashion:

monlangage_quater --> "a", star("a"), "b".

star(NT__0) --> "" | NT__0, star(NT__0).