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

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)."

Answer 1

Because it's loops as stated by others.

p.s the assignment has been extended to this thursday, so no need to panic [yet] and yeah, I know what assignment you're doing

Answer 2

The program will loop because of the search strategy adopted by Prolog. It tries to solve a query exploring the solution space with a depth first strategy, that is space efficient but incomplete.

Now should be clear that the solution space is infinite in your case, because of these loops in the graph. There are infinite paths from initial to final state.

Iterative deepening should be the simpler way to enumerate the paths, it's easy to implement in Prolog. Another possibility would be implementing a breadth first search.

Answer 3

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?