4. (Prolog and Finite Automata) [40 points total]

A nondeterministic finite automaton (or nondeterministic finite-state acceptor) is a state machine that allows more than one transition (or none at all) from a single state on a particular input character. Prolog can be used to simulate the execution of nondeterministic finite automata. Prolog is particularly adept at simulating acceptors, because, by default, Prolog answers queries with a "yes" (which could indicate acceptance of an input string) or "no" (which could indicate rejection of an input string).

(A) (10 points) Consider the nondeterministic finite automaton shown below. It takes binary strings as input. Describe in set notation and/or English what strings this automaton accepts.

Solution:

  This NFA accepts all binary strings consisting of
  alternating 1's and 0's whose length is 3 or greater.

(B) (30 points) Write a set of Prolog clauses that simulates the above NFA. Let one predicate be called nfa, having a behavior such that nfa(B) responds with yes if B is a binary string accepted by the above NFA. The query nfa(B) responds with no, if B is a binary string not accepted by the above NFA. In addition to defining nfa, you will likely want to add other, supporting, Prolog clauses. (Hint: Something like McCarthy's transformation may be helpful here.)

Assume B is represented as a list of zeros and ones. The reading of characters (bits) by the NFA progresses from left-to-right, so that the leftmost (first) element in B is read first by the NFA. The rightmost (last) element of B is read last.

Solution:

  nfa([1|R]) :- q2(R).
  nfa([0|R]) :- q1(R).
  q1([1|R])  :- q3(R).
  q2([0|R])  :- q4(R).
  q3([0|R])  :- q5(R).
  q3([0|R])  :- q4(R).
  q4([0|R])  :- q5(R).
  q4([0|R])  :- q3(R).
  q5([]).

  (It can be done in fewer predicates.)