There are many definitions of automata and transducers. The
differences between them consist mainly in the choice of symbols
describing particular items, in the way transitions are defined - as
a function, or as a relation, with various orderings of constituents,
and whether the 
-transitions are distinguished in the
definition. Notational differences are not important from the
theoretical point of view, but the choice of a particular suite of
definitions and notational conventions can simplify the description of
a problem, thus contributing to the clarity of explanations. The
suite of definitions given in this paper is based on two Watson's
papers ([Wat93a] and [Wat93b]), but is
converted to the notational convention found in
[HU79], which is regarded as the standard reference
for automata. However, we use different (equivalent) definitions where
it enhances the clarity of our discourse. The definitions for
finite-state transducers are taken mainly from [RS95].
We introduce a new type of automata: finite-state automata with final transitions. A transformation from the classical automata to the automata with final transitions is provided. We also discuss deterministic acyclic finite-state automata with final transitions. These automata are used in our implementation of the algorithms presented in this dissertation.