I cannot understand how Prolog knows what the start state is in a DFA accept rule

Question

I worded the title the best way I could think of, but let me make it clear. When programming a DFA in Prolog, here is a typical manner of doing so:

start(q0).
final(q2).

transition(q0, a, q1).
transition(q1, b, q1).
transition(q1, c, q2).

accept(Symbols) :- start(StartState), accept(Symbols, StartState).

accept([], State) :- final(State).

accept([Symbol|Symbols], State) :- transition(State, Symbol, NextState), 
                                accept(Symbols, NextState).

I understand what this code does, what its goal is, and all that. What boggles my mind are the "accept" rules. Again, I understand the logic behind what is being performed, but what I do not understand is the sudden usage of StartState and NextState. These just come out of nowhere, and I don't understand how start(StartState) would even return true to begin with, much less where the value comes from. The same with using NextState. What values does Prolog "think" is in these and how are they accepted by the transition facts?

If I start with the fact: start(q0)., then how is start(StartState). true?

Answer 1

While mat's answer is correct, I'll give you here a bit of operational semantics, i.e. how does it happen.

You ask, "If I start with the fact: start(q0)., then how is start(StartState). true?"

Answer: StartState is a logical variable. It doesn't have any value set to it yet. It is we that write this name, "out of nowhere" - it could be any name we choose; Prolog sees it, sees it's a new name (starting with an upper case letter), and creates a new logvar with that name, which is not yet instantiated (assigned a value). It's like a NULL pointer, which can be set only once at a later point (unless the system backtracks, but that's an orthogonal issue).

This is how Prolog works: it sees a query, start(X); it sees X is a new logvar; now it tries to prove this query. That means, it searches among all known facts and rules for such with head that matches our query.

There is one: it's the fact start(q0). Note q0 starts with a lower case letter. This means it's an atom, a symbolic datum. Variables start with upper case letters.

How does Prolog find the fact start(q0)? It just does. That's a detail of a given Prolog implementation. It finds it among all the facts and rules that constitute the program that we wrote, and loaded into Prolog.

Now the system matches start(q0) with start(X). This is called unification:

start(q0) = start(X)

this succeeds, with X = q0. A logvar X gets assigned its value, and the match succeeds. Thus the query is proven, with the substitution { X = q0 }.

This is how Prolog works.

But really, you should read a good Prolog tutorial, so that you understand all italicized words in the above. There will be even more issues to learn after that, so you could eventually be confident that you "understand" Prolog.

Answer 2

Well that's really the most trivial and basic thing: Given a fact

start(q0).

The query:

?- start(State).

succeeds and yields State = q0, which can be obviously deduced from the given fact, since this is exactly what the fact says: start(S) is true if S = q0.

Read your clauses declaratively, for example: If start(State) holds and Symbols are accepted starting from State, then accept(Symbols) holds. Try to read the other clauses in the same way, and it will become clear what they say.