Prolog query infinite search

Question

I am a beginner to Prolog and I would like to ask a question about Prolog.

My program is based on non-deterministic finite-state automaton.

the start state is S0 and the final state is S3.

The diagram is

enter image description here

so if there is a string [a,a,b,b,c,c] it should be like

start(s0).
edge(a, s0, s0).
edge(a, s0, s1).
edge(b, s1, s1).
edge(b, s1, s2).
edge(c, s2, s2).
edge(c, s2, s3).
final(s3).

There is a predicate accepts(Ls) if (there Ls is a list of string)

accepts(Ls) :- start(A), goesTo(Ls, A, B), final(B).

and assuming that the NFA goes from state Si to state Sj and in between them there is a state Sk, goesTo predicate is defined as

goesTo(Ls, Si, Sj) :- edge (L, Si, Sk), goesTo(Ls, Sk, Sj).

But if querying accepts(Ls) (any arbitrary list of string ranging from a to c) the tutorial question says that it will almost certainly go into an infinite search and stack overflow will occur.

However, I don't understand why the query will go into an infinite search and cause stack overflow. If you can give me the reason, it would be really great!

(edit:) the exact quote is:

"a typical Prolog user might hope that his/her goesTo rules would be such tat the query accepts(X) would generate successive strings that are accepted by the NFA above. Almost certainly, given the above presentation of the given NFA, the Prolog system will go into an infinite search and stack overflow will occur. Say why this is so. (if your goesTo avoid this problem, say how you managed to avoid it)."

Will Ness Will Ness · Accepted Answer · 2012-10-05T13:49:07

This is the definition of your NFA:

start(s0). 
edge(a, s0, s0). 
edge(a, s0, s1). 
edge(b, s1, s1). 
edge(b, s1, s2).
edge(c, s2, s2). 
edge(c, s2, s3).
final(s3).

It has no connection to any input string you might test for acceptance by it. Note the dots at the end of each line - these are Prolog predicates that define the NFA.

Running your accepts/1 with any concrete input string will result in finite recursion. The search space here is finite, and it will certainly be exhausted - provided you call accepts/1 with fully instantiated string of finite length.

Now, if you were to try to generate all the possible ~~paths~~ acceptable strings, then you'd have an infinite recursion because there are infinite number of acceptable strings:

a,b,c
a,a,b,c
a,a,a,b,c
a,a,a,a,b,c
.....

are all strings acceptable by this automaton.

Your predicate definitions all miss the final dot BTW. And goesTo is not quite right. It must be changed to:

goesTo([], S, S).
goesTo([L1|Ls], S1, Sn) :- edge(L1, S1, S2), goesTo(Ls, S2, Sn).
accepts(Ls) :- start(A), goesTo(Ls, A, B), final(B).

Also note, there must be no space between the predicate name and the opening parenthesis.

So now the OP have clarified their question. It is,

why an attempt to generate all possible acceptable strings will almost certainly go into an unproductive loop?

The call accepts(X) indeed goes into infinite recursion, because generation of a new node to try is restarted from the beginning, and so internally, an infinitely growing string of as is tried:

a
a,a
a,a,a
a,a,a,a
....

simply because edge(a,s0,s0) is the very first edge fact in the database, and the call to edge/3 is in the first position inside goesTo/3 predicate definition. And Prolog's search strategy is left-to-right.

We can get from totally unproductive behaviour (where Prolog just hangs in an infinite loop) to a productive behaviour by rearranging the goals like so:

start(s0). 
edge(a, s0, s1). 
edge(b, s1, s2).
edge(c, s2, s3).
edge(a, s0, s0). 
edge(b, s1, s1). 
edge(c, s2, s2). 
final(s3).

Now,

12 ?- accepts(X).

X = [a, b, c] ;
X = [a, b, c, c] ;
X = [a, b, c, c, c] ;
X = [a, b, c, c, c, c] ;
X = [a, b, c, c, c, c, c] ;
X = [a, b, c, c, c, c, c, c] ;
X = [a, b, c, c, c, c, c, c, c]

Unfortunately as can be seen the generation is skewed towards c. How to make it "fair"... let's leave it to another question, shall we?

Prolog query infinite search

3 Answers