Boost logo

Boost :

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

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

-----------------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();

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);

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,

Boost list run by bdawes at, gregod at, cpdaniel at, john at