Experiment in Automata syntax

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-06-02 09:29:33

Hello,
        I've been experimenting with a clean, usable syntax for representing 
automata. A skeletal implementation is at:

http://groups.yahoo.com/group/boost/files/Automata/automata_syntax.zip

-----------------DFA Creation Syntax-------------------
The syntax follows the theoretical syntax as closely as possible. Consider a 
simple DFA for the language a*ba*. The transition function delta for this 
language would be:

delta(q0, a) = q0;
delta(q0, b) = q1;
delta(q1, a) = q1;
delta(q1, b) = q2;
delta(q2, a) = q2;
delta(q2, b) = q2; 

q0 is the initial state, q1 is a final (accepting) state, and q2 is a trap 
state. The corresponding C++ code would be:

typedef boost::automata::dfa<ABAlphabet> DFA;
DFA dfa;

DFA::state q0 = dfa.add_state(false);
DFA::state q1 = dfa.add_state(true);

(q0, 'a') = q0;
(q0, 'b') = q1;
(q1, 'a') = q1;
(q1, 'b') = dfa.trap();
q0.set_initial();

The same syntax can be used for NFAs, and it is trivial to extend the syntax 
for PDA, TMs, etc.

-----------------Acceptor syntax------------------------
Acceptors are output iterators that apply the symbols output through them to 
the automata they are initialized with. For the above automata, we can test 
acceptance of standard input this way:
DFA::acceptor<> a = dfa.start();
copy(istream_iterator<char>(cin), istream_iterator<char>(), a);
if (a.accept()) {
  // accepted
}
else {
  // rejected
}

Acceptors can, of course, perform other more interesting tasks along with 
acceptance. Acceptors are parameterized by a visitor type whose enter_state 
and transition methods are executed when the acceptor enters a state or 
crosses a transition, respectively.

Now an example of using acceptors to create a Mealy machine. A Mealy machine 
is a DFA that also has an output language and, at each transition, has an 
output symbol in addition to the input symbol. When that transition is taken, 
it outputs the output symbol. We can construct one using a transition 
decorator and a visitor class. First, the visitor:

struct MealyVisitor {
      template<typename State>
      static void enter_state(const State&) {}
      
      template<typename Transition>
      static void transition(const Transition& trans) {
        std::cout << trans.decorator() << std::endl;
      }
};

And now create a simple DFA with a 'char' transition decorator:

// DFA has string decorators for the states and char decorators for 
// transitions
typedef boost::automata::dfa<ZeroOneAlphabet, std::string, char> DFA;
DFA dfa;

DFA::state q0 = dfa.add_state(true, "even");
DFA::state q1 = dfa.add_state(true, "odd");

(q0, 0) = transition(q0, 0);
(q0, 1) = transition(q1, 1);
(q1, 0) = transition(q1, 1);
(q1, 1) = transition(q0, 0);
q0.set_initial();

DFA::acceptor<MealyVisitor> a = q0.start(MealyVisitor());
copy(istream_iterator<int>(cin), istream_iterator<int>(), a);
if (a.accept()) { /* ... */ };

A Moore machine (outputs on entering a state) could be similarly constructed, 
and I believe the concept scales well to automata for richer language classes.

        Comments always welcome,
        Doug