Re: Experiment in Automata syntax

From: Vladimir Prus (ghost_at_[hidden])
Date: 2001-06-18 06:11:23

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?
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.
 

> -----------------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. 

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.

-- 
Regards,
Vladimir