next up previous
Next: About this document ... Up: Generic programming on automata Previous: Remark

Applying algorithms

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