Re: Experiment in Automata syntax

From: vincent.lemaout_at_[hidden]
Date: 2001-06-21 16:59:47

Hi,

D. Revuz and I have been working on ASTL and we sure would be pleased
if the
library could benefit from remarks, works and enhancements from you
all (there is still so much do be done).

--- In boost_at_y..., Vladimir Prus <ghost_at_c...> wrote:
> 
> Douglas Gregor wrote:
> > 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. 
> > [snip]
> > 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') = fa.trap();
> > q0.set_initial();
> 
> I have two points:
> 1) I'm a little concerned about q0.set_initial(). In your
> dfa_state_handle both pointer to dfa and state index is stored.
> How extra memory consumption due to dfa pointer will affect
performace?
> Is alternative implementation possible? Maybe, DFA::state should
have no
> operations at all?

That's the design decision we took from the start. We met no specific
problems with it that could make us change our mind. In fact, there is
no point in making a state a "complex" object. I think its sufficient
to consider it a handler to a data structure stored in the DFA
container, we rather store the pointer to the container
is objects called cursors which are DFA iterators allowing the
traditional uncoupling of the algorithm and the container. Here is the
idea : a cursor is a pointer to a state or a transition of the DFA (a
triple (state, letter, state)) allowing traversal of the
underlying container. The interface looks like this :

template <class DFA>
class cursor
{
public:
   State src() const;   // return the state the cursor is pointing to
   bool src_final() const; // return true if pointing to a
final                                  // (accepting) state
   bool forward(Alphabet);  // if the asked outgoing transition
is                                 // defined move along it and return
true                               // otherwise move to the "sink"
state
                            // and return false
   bool sink() const;       // return true if the cursor is
pointing                            // to the sink state
   bool exists(Alphabet) const; // return true if the
outgoing                                         // transition is
defined
   // .... a few methods more
};

The interesting thing here is that you can write adapters performing
any operation
"on-the-fly" during the traversal. For instance intersection :

template <class Cursor1, class Cursor2>
class intersection_cursor
{
  Cursor1 c1;
  Cursor2 c2;

  // ....
  bool forward(Alphabet a) {
    return c1.forward(a) && c2.forward(a);
};

> 2) I never thought about trap() state. Are complete automatons used
often 
> enough to justify special method for their support?. Even if they
are 
> usefull, they are likely to demand considerably more memory.
>  

This is what I call the sink state, if I get it right. The behavior of
the cursor
makes virtually all automata complete with undefined transitions
directed to the sink, most of the time the handler 0 which does not
mean they are actually stored in the structure. Let's call them sink
transitions.
You may need, as in the example, to change locally the destination of
the sink transition. The trick we use is to decide that a special
letter will used to define those transitions. They will be chosen by a
cursor adapter whenever the requested transition is undefined :

template <class Cursor>
class default_transition_cursor
{
   Cursor c;
   Cursor::Alphabet default_letter;

   // ....
   bool forward(Alphabet a) {
     if (c.exists(a)) return c.forward(a);
     else return c.forward(default_letter);
   }
   // ....
};

> 
> > -----------------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. 
> > [snip]
> 
> I find that acceptors are really usefull. 
> 

I agree. Not far from the cursors, just a matter of interface. Here is
how it is written in ASTL :

template <class InputIterator, class Cursor>
bool is_in (InputIterator first, InputIterator last, Cursor c)
{
  if (c.sink()) return false;
  for(; first != last && c.forward(*first); ++first);
  return first == last && c.src_final();
}

With a few helper functions, it is possible for instance to check if a
word is in the language recognized by the intersection of two DFAs
with one code line :

DFA_matrix< > A1, A2;
string w("word");
if (is_in(w.begin(), w.end(), intersectionc(A1, A2)))
  cout << "found";

Of course, the same apply for more complex traversal like depth-first
search (there is a depth_first_cursor)

> As a closing remark, I'd like to say that I will like automata
library to be 
> created. The simplest way would be through enhancing ASTL, if 
> its authors are still willing to boostify it -- after thinking about
ASTL's 
> cursors, I find them a good thing to have and the library already
has several 
> dfa classes and algorithms.
> 

Yes, I think cursors are good concepts we should investigate further
and there couldn't be any reason not to "boostify" it :-)

Regards.

Vincent.