1

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.

Nobody
  • 103
  • 8
  • This is cross posted on SWI-Prolog Discourse forum. ([ref](https://swi-prolog.discourse.group/t/how-to-program-a-list-in-prolog-that-can-contain-only-the-character-a-but-must-finish-with-the-character-b/4716?u=ericgt)) – Guy Coder Dec 05 '21 at 21:27

2 Answers2

4

Using Prolog's -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).
false
  • 10,264
  • 13
  • 101
  • 209
  • Nice to see others starting to add the `set_prolog_flag` and `use_module` for these DCG answers. It took me an extra 6 months of learning DCGs to figure out those were missing from answers posted here long ago. Thus adding the `DCG` tag here and noting [DCG info](https://stackoverflow.com/tags/dcg/info). – Guy Coder Dec 06 '21 at 22:46
  • @GuyCoder: Only an extra half-year? It took me much more to realize that this C&M chapter is not only for linguists as I was told in 1986. – false Dec 07 '21 at 12:34
  • And then we wonder why there are so few people who will hang in to really understand the beauty that Prolog can bring. – Guy Coder Dec 07 '21 at 12:36
  • @GuyCoder: Did you read *If you have difficulties installing `double_quotes.pl` as a library, simply put it into the directory of your other Prolog files and say: `use_module(double_quotes).`*? – false Dec 07 '21 at 14:01
  • [Here](https://stackoverflow.com/a/8269897/772868). – false Dec 07 '21 at 14:36
  • No, that again is a link that leads to a SO answer. This is what I was expecting. [http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/double_quotes.pl](http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/double_quotes.pl). A simple click then the code. – Guy Coder Dec 07 '21 at 14:51
4

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).
DuDa
  • 3,718
  • 4
  • 16
  • 36
  • Thanks a lot that's exactly what i wanted. – Nobody Dec 07 '21 at 10:21
  • But if I wanted to program a list in Prolog that must start with only one character a, and can contain n number of b? For example : a,b is correct, a,b,b,b,b,b is correct, a is incorrect, b,b,b is incorrect and a,a,b is incorrect. How should I do this please? – Nobody Dec 07 '21 at 10:25
  • I'll edit my answer. – DuDa Dec 07 '21 at 10:28
  • Very sorry to trouble you yet again, I still have three other problems that i can't code let's start with this one : How can I make a program that contains this time n numbers of a and n numbers of b, it's important to note here that the number a and b in the list must be equal, also the list must always start with a and finish with b, otherwise it's false. Exemple : [a,b] is true, [a,a,a,b,b,b] is true, [a,a,a,a,a,a,b,b,b,b,b,b] is true. But [a,a,b] is false, [a,a,a] or [b,b,b] is false and [a,b,b,b] or [b,b,a,a] is also false. Thank you very much for your help again. – Nobody Dec 08 '21 at 11:48
  • @Nobody it is best to open a new question and provide your attempt. People here (including me) like to solve issues but just getting solutions will not help you understand prolog. So make a new question, show us what you tried and ask specific questions. – DuDa Dec 08 '21 at 12:05
  • Alright, i'll show u what i did in a new question. – Nobody Dec 08 '21 at 14:51
  • Here is the link of my new question : https://stackoverflow.com/questions/70277140/how-to-program-a-list-in-prolog-that-must-contain-only-characters-a-and-b-and-o – Nobody Dec 08 '21 at 15:09
  • hello sorry to bother you but after I added: langage([]). to your code, it's wrong now. Cause I want to make the list empty true in our case. langage([a,b]). langage([a | S]):- langage(S). – Nobody Dec 08 '21 at 19:48
  • @Nobody I guess you need an auxillary predicate like in the second case (`langage/1` and `langageB/1`). By just adding `langage([]).` you allow 2 types of words: the words start with an arbitrary number of a's and end with either ab or nothing. – DuDa Dec 09 '21 at 08:16