2.14 DFA parser

The following program simulates a parser/acceptor for an arbitrary deterministic finite automaton (DFA). When this and a state table program are loaded into Prolog, the parser/acceptor may be used to check inputs to the DFA to see whether or not they are acceptable. The program traces its action using write statements; these have been indented in order to better display the logical structure of the clauses.

parse(L) :- start(S), 
            trans(S,L).

trans(X,[A|B]) :- 
      delta(X,A,Y),   /*  X ---A---> Y */
      write(X),
      write('  '),
      write([A|B]),
      nl,
      trans(Y,B).  
trans(X,[]) :- 
      final(X),
      write(X),
      write('  '),
      write([]), nl.

As an example, the following Prolog code specifies a state table for a DFA that accepts the language (a,b)*ab(a,b)* .

delta(0,a,1).   
delta(0,b,0).
delta(1,a,1).
delta(1,b,2).
delta(2,a,2).
delta(2,b,2).
 
start(0).

final(2).

A state diagram for this machine is as follows:

Fig. 2.14

Suppose that both the driver program and the state table program are loaded ...

?- parse([b,b,a,a,b,a,b]).
0  [b,b,a,a,b,a,b]
0  [b,a,a,b,a,b]
0  [a,a,b,a,b]
1  [a,b,a,b]
1  [b,a,b]
2  [a,b]
2  [b]
2  []
yes

?- parse([b,b,a]).
0  [b,b,a]
0  [b,a]
0  [a]
no

Exercise 2.14 Modify dfadrivr.pro so that it becomes a parser for NFAs, nondeterministic finite automata. Why is this extension such a natural one for Prolog?

Exercise 2.15 Using the DFA simulator presented here as motivation, design a Prolog simulator for Turing machines.