Next: About this document ...
Up: Generic programming on automata
Previous: Remark
This section shows how to apply algorithms to an automaton. In this more
complex example, we
create an automaton with a list of word read from standard input (we create a
tree-like automaton with the algorithm trie), then we minimize it with the
algorithm acyclic_minimization, we put it in a compact automaton which
we save to disc (method write) and we eventually write on standard
output the recognized language of the automaton (algorithm
dfa_language). First of all, here are the preconditions imposed on the
tag and dfa types in order to have these algorithms work and their prototypes
:
//
// Algorithm : trie
// Description : creates a trie with a list of Strings
// Input : a dfa, a range on a container holding String values
// Output : result is placed in the first argument
// Precondition : *start is of type String
// Remark : reads strings until finish iterator is reached
//
template <class DFA, class InputIterator>
void trie(DFA &result, InputIterator start, InputIterator finish);
//
// Algorithm : acyclic_minimization
// Description : minimize an acyclic dfa
// Input : a dfa
// Output : result is written in the argument
// Precondition : dfa must be acyclic
// : long Tag::mark()
// : void Tag::mark(long)
// : long Tag::trans()
// : void Tag::trans(long)
// : bool Tag::final()
// : void Tag::final(bool)
//
template <class DFA>
void acyclic_minimization(DFA &A);
//
// Algorithm : language
// Description : computes the recognized language of a dfa
// Input : a dfa
// Output : result is written on standard output
// Precondition : none
//
template <class DFA, class OutputIterator>
void language(DFA &A, OutputIterator out);
--- beginning of file ---
#include "dfa_map.hh"
#include "dfa_compact.hh"
#include "alphabet.hh"
#include "tag.hh"
#include "dfalgo_trie.hh"
#include "dfalgo_lang.hh"
#include "dfalgo_mini.hh"
#include <iterator.h>
#include <String.h>
#include <iostream.h>
class Tag : public STag
{
protected:
long _mark;
long _trans;
public:
long mark() { return _mark; }
void mark(long l) { _mark = l; }
long trans() { return _trans; }
void trans(long l) { _trans = l; }
Tag() : STag() { }
};
main()
{
typedef DFA_matrix<Range_alphabet<char, 'a', 'z'>, Tag> DFA_type;
DFA_type dfa;
// Creates the trie
trie(dfa, istream_iterator<String>(cin), istream_iterator<String>());
// Minimizes the automaton
acyclic_minimization(dfa);
// Compacts the automaton
DFA_compact<DFA_type> dfa_c(dfa);
// Dumps the language
language(dfa, ostream_iterator<char>(cout));
}
--- end of file ---
Vincent Lemaout
12/9/1997