# 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