0

How can I make a program in Prolog that contains n numbers of a and n numbers of b, it's important to note here that the number of 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. Example : [a,b] is true, [a,a,a,b,b,b] is true, [a,a,a,a] is false and [a,a,a,b,b] is also false.

Here is what I tried to do :

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

language([]).

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

But it does not work as I want it to.

Nobody
  • 103
  • 8
  • @DuDa, I really hope you can help me. Basically, I just tried to make the list contain only n characters of a and n characters of b, but I don't know how I could make langage([a| S]):- langageB(S) == langage([a | S]):- langage(S). So that prolog returns true only if the number of a and b are equal. Thank you very much for your time. – Nobody Dec 08 '21 at 15:07
  • Typo! Easy to catch if empty lines are only between different predicates. – false Dec 08 '21 at 17:11

3 Answers3

3

Using DCG notation, the desired language can be defined as:

langage --> [a,b].
langage --> [a], langage, [b]. % For each a at the beginning of the list 
                               % there must be a corresponding b at the end

langage(List) :- phrase(langage, List).

Examples:

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

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

?- langage(L).
L = [a, b] ;
L = [a, a, b, b] ;
L = [a, a, a, b, b, b] ;
L = [a, a, a, a, b, b, b, b] .

If you want to see how to define the predicate directly using difference lists, you can list the clauses of the predicate langage/2:

?- listing(langage).

langage([a, b|A], A).

langage([a|A], B) :-
    langage(A, C),
    C=[b|B].

So, an alternative solution is:

langage(List) :-
  langage(List, []).

langage([a, b|A], A).

langage([a|A], B) :-
    langage(A, C),
    C = [b|B].
slago
  • 5,025
  • 2
  • 10
  • 23
  • @slago Thanks a lot, that's exactly what I wanted, I'll be using the alternative solution cause it's easier for me to understand. But I just have another question on this link about another problem in prolog about reversing a list containing only {a,b}: https://stackoverflow.com/questions/70279750/how-to-program-with-prolog-using-lists-to-evaluate-if-any-word-in-our-language-w – Nobody Dec 08 '21 at 18:10
3
langage --> [a], ( [] | langage ) , [b].

?- phrase(langage, Xs).
   Xs = "ab"
;  Xs = "aabb"
;  Xs = "aaabbb"
;  Xs = "aaaabbbb"
;  Xs = "aaaaabbbbb"
;  ... .
false
  • 10,264
  • 13
  • 101
  • 209
1

Assuming e.g. [a, b, a, b] is an acceptable list:

go :-
    findnsols(20, ABs, ab_list(ABs), ABsLst), !,
    writeln(ABsLst).


ab_list(ABsWrapped) :-
    length(ABs, Len),
    ab_list_(Len, 0, [], ABs),
    append([[a], ABs, [b]], ABsWrapped).


ab_list_(0, 0, ABs, ABs) :- !.

ab_list_(CharsToAdd, Bal, SoFar, ABs) :-
    succ(CharsToAdd0, CharsToAdd),
    add_char(Char, Inc),
    Bal1 is Bal + Inc,
    % Ensure that the balance can be zero for the complete list
    CharsToAdd0 >= abs(Bal1),
    ab_list_(CharsToAdd0, Bal1, [Char|SoFar], ABs).

add_char(b, -1).
add_char(a, 1).

Results:

?- time(go).
[[a,b],[a,a,b,b],[a,b,a,b],[a,a,a,b,b,b],[a,a,b,a,b,b],[a,b,a,a,b,b],[a,a,b,b,a,b],[a,b,a,b,a,b],[a,b,b,a,a,b],[a,a,a,a,b,b,b,b],[a,a,a,b,a,b,b,b],[a,a,b,a,a,b,b,b],[a,b,a,a,a,b,b,b],[a,a,a,b,b,a,b,b],[a,a,b,a,b,a,b,b],[a,b,a,a,b,a,b,b],[a,a,b,b,a,a,b,b],[a,b,a,b,a,a,b,b],[a,b,b,a,a,a,b,b],[a,a,a,b,b,b,a,b]]
    % 935 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 1419728 Lips)

Original: Here's a (very inefficient) solution as a one-liner in swi-prolog:

length(As, 2), same_length(As, Bs), maplist(=(a), As), maplist(=(b), Bs), append([As, Bs], ABs), distinct(ABsPerm, permutation(ABs, ABsPerm)), append([[a], ABsPerm, [b]], Final).
brebs
  • 3,462
  • 2
  • 3
  • 12