previousnext
ASTL homeSTL home

Copy_depth

 

Prototype

template <class DFA1, class DFA2, class TagAssignement> 
void depth_copy(DFA2 &to,const DFA2 &from, TagAssignement ta);

Description

Copy dfa1 into dfa2 using a depth first search

Definition

Defined in copy.h.

Requirements on types

Preconditions

DFA1::Alphabet must be castable to DFA2::Alphabet.

Example

CODE
OUTPUT

#include <tag.h>
#include <dfa_matrix.h>
#include <alphabet.h>
#include <language.h>
#include <iterator>
#include <iostream.h>
#include <copy.h>

//first, declaring an appropriate assignement function
class assign {
minimization_tag operator() (minimization_tag &t, const default_tag &u)
{return (t);}
};

//code corresponding to the DFA example, without
//the 10 to 8 transition, in order to avoid cyclicity (for language)


main()
{
//spécifie the type of the DFA
typedef DFA_matrix<Range_alphabet<char,'a','g'>,default_tag> DFA_type;
typedef DFA_map<Range_alphabet<char,'a','z'>,default_tag> DFA2_type;

//initialising the DFA, empty

DFA_type dfa;

//creating and adding the states
DFA_type::State s[11];
for(int i=1;i<=10;i++)
s[i]=dfa.new_state();

//setting the transitions

dfa.set_trans(s[1],'a',s[2]);
dfa.set_trans(s[1],'b',s[3]);
dfa.set_trans(s[2],'f',s[4]);
dfa.set_trans(s[2],'b',s[5]);
dfa.set_trans(s[3],'c',s[6]);
dfa.set_trans(s[4],'g',s[7]);
dfa.set_trans(s[4],'e',s[9]);
dfa.set_trans(s[5],'g',s[8]);
dfa.set_trans(s[6],'b',s[5]);
dfa.set_trans(s[6],'d',s[8]);
dfa.set_trans(s[6],'e',s[10]);
dfa.set_trans(s[8],'d',s[10]);

//declaring initial and finals states...VERY IMPORTANT...
dfa.initial(s[1]);
dfa.final(s[5])=true;
dfa.final(s[9])=true;
dfa.final(s[10])=true;

//writing the language on the standart output

cout<<"orignal DFA"<<endl;
language(dfa,ostream_iterator<DFA_type::Alphabet>(cout));
cout<<"copied DFA"<<endl;
assign A;
depth_copy(dfa2,dfa,A);
language(dfa2,ostream_iterator<DFA_type::Alphabet>(cout));

}

# ./copy_breadth
orignal DFA
ab
abgd
afe
bcb
bcbgd
bcdd
bce
copied DFA
ab
abgd
afe
bcb
bcbgd
bcdd
bce

Notes

See also

copy_breadth