fmp_transducer_maker.thxx 6.95 KB
Newer Older
Michaël Cadilhac's avatar
Michaël Cadilhac committed
1
//							-*- C++ -*-
2
// fmp_transducer_maker.thxx: this file is part of the Vaucanson project.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
3
//
4
// Vaucanson, a generic library for finite state machines.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
5
//
6
// Copyright (C) 2005, 2006, 2008 The Vaucanson Group.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
7
//
8
9
10
11
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
12
//
13
// The complete GNU General Public Licence Notice can be found as the
14
// `COPYING' file in the root directory.
Michaël Cadilhac's avatar
Michaël Cadilhac committed
15
//
16
// The Vaucanson Group consists of people listed in the `AUTHORS' file.
17
//
Michaël Cadilhac's avatar
Michaël Cadilhac committed
18

19
/*
Akim Demaille's avatar
Akim Demaille committed
20
 * CPP guard should not be inserted here as
Michaël Cadilhac's avatar
Michaël Cadilhac committed
21
22
23
24
 * VCSN_CONTEXT_NAMESPACE could be changed.
 */

#include <vaucanson/algorithms/minimization_hopcroft.hh>
25
#include <vaucanson/algorithms/evaluation_fmp.hh>
Michaël Cadilhac's avatar
Michaël Cadilhac committed
26
27
28
#include <vaucanson/algorithms/aut_to_exp.hh>
#include <vaucanson/algorithms/trim.hh>
#include <vaucanson/algorithms/realtime.hh>
29

30
31
namespace vcsn
{
32
  namespace VCSN_GRAPH_IMPL
33
  {
34
    VCSN_CONTEXT_NAMESPACE
35
    {
36

37
38
      template <class FirstInputIterator, class SecondInputIterator>
      automata_set_t make_automata_set(const FirstInputIterator first_begin,
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
	const FirstInputIterator first_end,
	const SecondInputIterator second_begin,
	const SecondInputIterator second_end,
	const monoid_rep_t& mrep =
	*(vcsn::algebra::monoid_rep_default<monoid_t>::get_instance()),
	const first_monoid_rep_t& mrep1 =
	*(vcsn::algebra::monoid_rep_default<first_monoid_t>::get_instance()),
	const second_monoid_rep_t& mrep2 =
	*(vcsn::algebra::monoid_rep_default<second_monoid_t>::get_instance()),
	const series_rep_t& srep =
	*(vcsn::algebra::series_rep_default<semiring_t, monoid_t>::get_instance()),
	const first_series_rep_t& srep1 =
	*(vcsn::algebra::series_rep_default<semiring_t, first_monoid_t>::get_instance()),
	const second_series_rep_t& srep2 =
	*(vcsn::algebra::series_rep_default<semiring_t, second_monoid_t>::get_instance()))
54
55
56
57
58
59
60
61
62
63
      {
	first_alphabet_t	first_alpha;
	for (FirstInputIterator e = first_begin; e != first_end; ++e)
	  first_alpha.insert(*e);

	second_alphabet_t	second_alpha;
	for (SecondInputIterator e = second_begin; e != second_end; ++e)
	  second_alpha.insert(*e);

	semiring_t		semiring;
64
65
66
67
68
69
70
	first_monoid_t		mA(first_alpha, mrep1);
	second_monoid_t		mB(second_alpha, mrep2);
	monoid_t		freemonoidproduct(mA, mB, mrep);
	// FIXME: srep1 and srep2 cannot be used.
	series_set_t		series(semiring, freemonoidproduct, srep);

	return automata_set_t(series);
71
72
73
74
75
      }


      template <class FirstInputIterator, class SecondInputIterator>
      automaton_t make_automaton(const FirstInputIterator first_begin,
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
	const FirstInputIterator first_end,
	const SecondInputIterator second_begin,
	const SecondInputIterator second_end,
	const monoid_rep_t& mrep =
	*(vcsn::algebra::monoid_rep_default<monoid_t>::get_instance()),
	const first_monoid_rep_t& mrep1 =
	*(vcsn::algebra::monoid_rep_default<first_monoid_t>::get_instance()),
	const second_monoid_rep_t& mrep2 =
	*(vcsn::algebra::monoid_rep_default<second_monoid_t>::get_instance()),
	const series_rep_t& srep =
	*(vcsn::algebra::series_rep_default<semiring_t, monoid_t>::get_instance()),
	const first_series_rep_t& srep1 =
	*(vcsn::algebra::series_rep_default<semiring_t, first_monoid_t>::get_instance()),
	const second_series_rep_t& srep2 =
	*(vcsn::algebra::series_rep_default<semiring_t, second_monoid_t>::get_instance()))
91
92
      {
	return automaton_t (make_automata_set(first_begin, first_end,
93
94
			    second_begin, second_end,
			    mrep, mrep1, mrep2, srep, srep1, srep2));
95
96
97
98
      }

      template <class T1, class T2>
      automaton_t make_automaton(const T1& first_alphabet,
99
100
101
102
103
104
105
106
107
108
109
110
111
	const T2& second_alphabet,
	const monoid_rep_t& mrep =
	*(vcsn::algebra::monoid_rep_default<monoid_t>::get_instance()),
	const first_monoid_rep_t& mrep1 =
	*(vcsn::algebra::monoid_rep_default<first_monoid_t>::get_instance()),
	const second_monoid_rep_t& mrep2 =
	*(vcsn::algebra::monoid_rep_default<second_monoid_t>::get_instance()),
	const series_rep_t& srep =
	*(vcsn::algebra::series_rep_default<semiring_t, monoid_t>::get_instance()),
	const first_series_rep_t& srep1 =
	*(vcsn::algebra::series_rep_default<semiring_t, first_monoid_t>::get_instance()),
	const second_series_rep_t& srep2 =
	*(vcsn::algebra::series_rep_default<semiring_t, second_monoid_t>::get_instance()))
112
113
      {
	return make_automaton(first_alphabet.begin(), first_alphabet.end(),
114
115
			      second_alphabet.begin(), second_alphabet.end(),
			      mrep, mrep1, mrep2, srep, srep1, srep2);
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
      }

      template <class FirstIterator, class SecondIterator>
      monoid_elt_t make_couple(const FirstIterator first_begin,
			       const FirstIterator first_end,
			       const SecondIterator second_begin,
			       const SecondIterator second_end,
			       const std::string& first_exp,
			       const std::string& second_exp)
      {
	first_alphabet_t	first_alpha;
	for (FirstIterator e = first_begin; e != first_end; ++e)
	  first_alpha.insert(*e);

	second_alphabet_t	second_alpha;
	for (SecondIterator e = second_begin; e != second_end; ++e)
	  second_alpha.insert(*e);

	monoid_t		fmp (first_alpha, second_alpha);
	monoid_elt_value_t	fmp_elt_value (first_exp, second_exp);

	return Element<monoid_t, monoid_elt_value_t> (fmp, fmp_elt_value);
      }

      template <class T1, class T2>
      monoid_elt_t make_couple(const T1& first_alphabet,
			       const T2& second_alphabet,
			       const std::string& first_exp,
			       const std::string& second_exp)
      {
	return make_couple(first_alphabet.begin(), first_alphabet.end(),
			   second_alphabet.begin(), second_alphabet.end(),
			   first_exp, second_exp);
      }


      template <typename TransStruct,
	        typename TransImpl,
	        typename SeriesStruct,
	        typename SeriesImpl,
	        typename S,
	        typename T>
      AUTOMATON_CONTEXT::rat_exp_t
      do_evaluation(const vcsn::AutomataBase<TransStruct>&,
		    const TransImpl&,
		    const SeriesStruct&,
		    const vcsn::rat::exp<S, T>& input,
		    const Element<TransStruct, TransImpl>& t,
		    const Element<SeriesStruct, SeriesImpl>&)
      {
	AUTOMATON_CONTEXT::automaton_t w = AUTOMATON_CONTEXT::make_automaton(t.structure().series()
	    .monoid().first_monoid().alphabet());
	AUTOMATON_CONTEXT::automaton_t result = AUTOMATON_CONTEXT::make_automaton(t.structure().series()
	    .monoid().second_monoid().alphabet());
	standard_of(w, input);
	evaluation_fmp(t, quotient(w), result);

	return aut_to_exp(generalized(quotient(realtime(trim(result)))),
	    DMChooser());
      }


      template <typename TransStruct,
	        typename TransImpl,
	        typename ArgStruct,
	        typename ArgImpl>
      AUTOMATON_CONTEXT::rat_exp_t
      evaluation(const Element<TransStruct, TransImpl>& t,
		 const Element<ArgStruct, ArgImpl>& input)
      {
	return do_evaluation(t.structure(), t.value(),
			     input.structure(), input.value(),
			     t, input);
      }


    } // End of VCSN_CONTEXT_NAMESPACE.
  } // End of VCSN_GRAPH_IMPL.
194
} // End of namespace vcsn.
195