** Next:** Transducers with Predicates and
** Up:** Operations on recognizers
** Previous:** Complementation

In Hopcroft's minimization algorithm
[12,1] a situation arises very similar to
the determinization case. In this minimization algorithm, a partition
of states is repeatedly refined by considering a pair of state and
symbol which might reveal that an existing subset must be split.
Rather than considering a pair of state and symbol, we consider in the
generalization a pair of state and `exclusive' predicate. As in the
determinization algorithm we therefore need to consider all boolean
combinations over the predicates present on a given state. In the
actual implementation, we re-use the additional code required for the
determinization algorithm in the implementation of the minimization
algorithm.
The generalized minimization algorithm produces a pfsr that is minimal
in the number of states. However, the pfsr is not necessarily unique,
and could also be non-minimal in the number of transitions. This is
caused by the fact that the predicates used in the pfsr might not be
sufficiently general. For example, the language {a,*b*,*c*} can be
presented with a 2-state automaton with a single transition labeled
, but e.g. also with a 2-state automaton with two
transitions labeled respectively by and .
Therefore, the minimization of a pfsr includes a final * cleanup*
step in which for each pair of states *p* and *q* all transitions from
*p* to *q* with labels
are combined into a single
transition from *p* to *q* with associated label
. It turns out that in the case of
transducers, the corresponding cleanup operator is more difficult, as
we discuss in section 5.1.

** Next:** Transducers with Predicates and
** Up:** Operations on recognizers
** Previous:** Complementation
*Noord G.J.M. van*

*2001-06-22*