previousnext
ASTL homeSTL home

Acyclic_minimization

 

Prototype

template <class DFA> 
void acyclic_minimization(DFA& A);

Description

Minimize A by identifying and fusionning its equivalents states.

Definition

Defined in minimize.h.

Requirements on types

Preconditions

A must be acyclic, which mean that no path starting from a given state ever encounter that state again.

Example

CODE
OUTPUT

#include <tag.h>
#include <dfa_matrix.h>
#include <alphabet.h>
#include <language.h>
#include <astl_tree.h>
#include <minimize.h>


main()
{

//spécifie the type of the DFA
typedef DFA_matrix<Type_alphabet<char>,minimization_tag > DFA_type;
typedef istream_iterator<vector<typename DFA_type::Alphabet> > Entry;

//initialising the DFA, empty

DFA_type dfa;

//creating states and transitions . . .
cout<<"enter words (return to separe, ctr-D to end)"<<endl; tree_build(dfa,Entry(cin),Entry());

//writing the language on the standart output
cout<<"words reconized by your DFA"<<endl;
language(dfa,ostream_iterator<DFA_type::Alphabet>(cout));
cout<<"nombre d'etats:"<<dfa.state_count()<<endl;

//minimizing
cout<<"now minimizing"<<endl;
acyclic_minimization(dfa);
cout<<"nombre d'etats:"<<dfa.state_count()<<endl;

//rewritting the language (to ensure equivalence)
cout<<"language...again..."<<endl;
language(dfa,ostream_iterator<DFA_type::Alphabet>(cout));

}

# ./minimize
enter words (return to separe, ctr-D to end)
stl
astl
template
iterator
input iterator
container
function
function object
functor

words reconized by your DFA
astl
container
function
function object
functor
input iterator
iterator
stl
template
nombre d'etats:63
now minimizing
nombre d'etats:46
language...again...
astl
container
function
function object
functor
input iterator
iterator
stl
template

Notes

See also