Checking if a string is contained in a language (Prolog)

Question

This is the CFG:

S -> T | V
T -> UU
U -> aUb | ab
V -> aVb | aWb
W -> bWa | ba

so this will accept some form of:

{a^n b^n a^m b^m | n,m >= 1} U {a^n b^m a^m b^n | n,m >= 1}

And here is the code I'm working with:

in_lang([]).  
in_lang(L) :-
    mapS(L), !.

mapS(L) :-
    mapT(L) ; mapV(L),!.

mapT(L) :-
    append(L1, mapU(L), L), mapU(L1), !.

mapU([a|T]) :-
    ((append(L1,[b],T), mapU(L1)) ; (T = b)),!.

mapV([a|T]) :-
    ((append(L1,[b],T), mapV(L1)) ; 
     (append(L1,[b],T), mapW(L1))),
    !.

mapW([b|T]) :-
    ((append(L1,[a],T), mapW(L1)) ;
     (T = a)),
    !.

As of right now, this is returning false for the following three strings:

[a,a,b,b,a,b] // this should be true
[a,a,a,b,b,a,a,b,b,b] // this should be true as well
[a,a,a,b,b,a,b,b,b] // this one IS false

Any help or insight would be greatly appreciated, I'm not too comfortable with Prolog so debugging this by myself has been a challenge.

All these cuts (`!`), what are they for? A cut at the very end of a predicate definition is a very strong code smell. — , Apr 25 '16 at 15:39

false · Answer 1 · 2022-08-19T11:10:55.207

6

Simply use a dcg! And library(double_quotes).

:- set_prolog_flag(double_quotes, chars).

s --> t | v.
t --> u, u.
u --> "a",u,"b" | "ab".
v --> "a",v,"b" | "a",w,"b".
w --> "b",w,"a" | "ba".

?- use_module(library(double_quotes)).

?- length(L,N), phrase(s, L).
   L = "abab", N = 4
;  L = "abab", N = 4
;  L = "aabbab", N = 6
;  L = "abaabb", N = 6
;  L = "aababb", N = 6
;  L = "abbaab", N = 6
;  L = "aaabbbab", N = 8
;  L = "aabbaabb", N = 8
;  L = "abaaabbb", N = 8
;  L = "aaababbb", N = 8
;  ... .

edited Aug 19 '22 at 11:10

answered Apr 25 '16 at 15:58

false

10,264
13
101
209

1

That wouldn't make it much of a homework problem, no? – Scott Hunter Apr 25 '16 at 16:05
3

@ScottHunter From at least 1965 up to 1972 people stumbled wading in ignorance about that question: How to encode a grammar properly.They all tried some append-like beast. Let's not perpetuate this time of darkness. Since summer 1972 there is no excuse! – false Apr 25 '16 at 16:19
1

So the OP's apparent ignorance of dcg isn't a hint that maybe it wasn't meant to be used? Translating a CFG to dcg is a pretty trivial exercise, which makes it a good *solution* but lousy *homework*. Which was my point. – Scott Hunter Apr 25 '16 at 16:31
2

@ScottHunter To be fair, the problem statement _screams_ DCG. I wouldn't be too surprised if OP's "apparent ignorance" is exactly that. – Apr 25 '16 at 16:39
3

@ScottHunter: Matter of factly, there are still a lot of DCG-free Prolog courses. Which is next to an oxymoron: The discovery of the DCG-specific encoding was the very reason why Prolog was conceived, 44 years ago. Time for an update! – false Apr 25 '16 at 16:53

score 1 · Answer 2 · answered Apr 25 '16 at 15:48

1

In the definition of mapT, you are trying to use the "return value" of mapU as an argument to append. But mapU is a predicate, and predicates don't have return values.

Instead one typically writes a predicate with an unbound variable which the predicate binds to the desired "return value"; after the predciate has been proven, the now bound variable can be used in subsequent predicates.

answered Apr 25 '16 at 15:48

Scott Hunter

48,888
12
60
101

I originally tried doing T1 is mapU(L), mapU(T1). This, however, kept throwing an exception stating "ERROR is/2: Type error: '[]' expected, found '[a,a,b,b,a,b]' ("x" must hold one character)" and I'm not quite sure how to fix that while still using an unbound variable. – csh1579 Apr 25 '16 at 16:15
1

It is not at all clear from this description what you were trying to do, much less why it did not work. Maybe if you showed the actual code, and not just a description of an unidentified piece. – Scott Hunter Apr 25 '16 at 16:26

score 1 · Accepted Answer · answered Apr 25 '16 at 17:39

First, note that this code doesn't make sense:

... append(L1, mapU(L), L) ...

In Prolog there are predicates, not functions...

A CFG production rule (a non terminal) should 'eat' a number of tokens, and in Prolog this means you need at least 2 arguments: the input token list, and what remains after a production has successfully matched the relevant part of input.

That is, append/3 is not required: just pattern matching, performed by unification operator (=)/2

mapS(L1, L) :- mapT(L1,L) ; mapV(L1,L).
mapT(L1, L) :- mapU(L1,L2), mapU(L2,L).
mapU(L1, L) :- L1=[a|L2], mapU(L2,L3), L3=[b|L] ; L1=[a,b|L].
... complete the translation

and then call it:

?- mapS([a,a,b,b,a,b],R).
R = [] ;
false.

R = [] means the entire sequence has been matched...

Checking if a string is contained in a language (Prolog)

3 Answers3

Linked