Here we develop a formal definition for transducers exactly as we did for
DFAs and NDFAs.
Definition: Transducer
A
transducer is a 6-tuple
(Q,Σ,Γ,δ,s,W ),
where
- Q is the set of states (must be finite!)
- Σ is the input alphabet (must be finite!)
- Γ is the output alphabet (must be finite!)
- δ is a function,
δ: Q × Σ → Q × Γ*,
defining the transitions
- s is the start state, s ∈ Q
- W is the set of accepting states,
W ⊆ Q
Note that the transition function now returns the state
you move to and the string to be output.
Definition: Configuration
A configuration of transducer
M = (Q,Σ,Γ,δ,s,W) is a 3-tuple
(q,w,v) ∈ Q × Σ* × Γ*.
It is interpreted as "Machine M is in state q with
string w left on the input tape and string
v already written as output".
Definition: Yields in one step
For transducer M = (Q,Σ,Γ,δ,s,W) we say
that configuration (p,w,v) yields in one step
configuration (q,s,t) if for some character
a ∈ Σ and string x ∈ Γ* we have
w = as, t = vx, and δ(p,a) = (q,x).
This is sometimes denoted
(p,w,v) ⇒ (q,s,t), or
(p,w,v) ⇒M (q,s,t) when you need to
clearly indicate which machine you're referring to.
Just as before, we define "yields eventually", i.e.
⇒*, to mean there's some sequence of configurations
each yielding the next in one step. The next step for us
is to define precisely what we mean by the output of a
machine on a given input string.
Definition: string output by a transducer
Transducer M = (Q,Σ,Γ,δ,s,W)
outputs string s ∈ Γ* given string w
∈ Σ* as input
if (s,w,λ) ⇒* (q,λ,s) for some state
q ∈ W.
Note that according to this definition, a transducer only
produces a output for accepting computations. This is not
a limitation, since if you wanted output for every input
you could just make every state accepting. Finally, we
can define the output language for a transducer
Definition: Language output by a transducer
Transducer
M = (Q,Σ,Γ,δ,s,W)
has
output languge P(M) ⊆ Γ*
defined as follows:
P(M) = { s ∈ Γ* | for some
w ∈ Σ* machine M outputs
s on input w }
The following algorithm proves that for any regular language
L
there is a transducer whose output language is L.
Input: DFA M = (Q,Σ,δ,s,W)
Output: Transducer T =
(Q,Σ,Σ,δ',s,W)
where
δ'(p,x) = (δ(p,x),x)
This algorithm is really simple, since every time the
original machine reads a character, the transducer just
outputs it. Since srings are output only for
accepting computations, this gives us as output exactly the
input strings that were accepted by the original machine.
The other direction is more interesting, i.e. can we prove
that any language output by a trasducer is regular? The
answer is yes! But how ...