Re: [boost] [Graph] finite state automata algorithms challenge

From: Douglas Gregor (gregod_at_[hidden])
Date: 2000-10-25 13:38:21

On Wed, 25 Oct 2000 08:27:18 -0500 (EST)
Jeremy Siek <jsiek_at_[hidden]> wrote:

> Here's an interesting challenge project. Add finite state
> automata algorithms to boost, using the boost graph library.

I too have considered this project. Though I haven't had the time to implement it, I have a suggestion about the external interface to such a library that may be useful.

I based my design on an Acceptor concept, which is a refinement of an Output Iterator. The Acceptor concept adds a free function "accepts" to determine if the symbol string written to the Acceptor is accepted by the automata, e.g., 

MyAutomata::acceptor a = myAutomata.start();
string testString = "foo";
copy(string.begin(), string.end(), a);
if (accepts(a)) { 
  cout << testString << " was accepted" << endl; 
} else {
  cout << testString << " was rejected" << endl;
}

Clearly, there are more necessary refinements to Acceptor, but I believe the idea is sound. For instance, the acceptor for an NFA can reasonably evaluate on a per-symbol basis, making "accepts" calls relatively cheap, whereas a Turing machine acceptor may merely store the incoming symbols and run when "accepts" is called.

        Doug Gregor
        gregod_at_[hidden]