Class 26: Transducers part Deux


Reading
None.
Homework
  1. Consider the following transducer:
    Note that I use e instead of λ for the empty string, and that a trasition labeled +/e, for example, reads character + and outputs nothing A transition labeled ;/NUM reads character ; and outputs the string NUM.

    a. Write the tuple representing this transducer.

    b. What string is output by the transducer for

    • 101+0-11;
    • -11-10;
    • 101+;

  2. Why do I care about transducers? Output could be viewed as actions so, for example, a vending machine is a transducer. Draw a diagram for a machine that has Coke (C) and water(W), costing 25 and 50 cents, respectively. It only takes quarters. Inputs are therefore Q = "insert quarter", C = "select coke", W = "select water", R = "coin return". Outputs are: C = "give out coke", W = "give out water", and Q = "give back one quarter". Here are some examples of inputs and outputs:
    • Input: QQW, Output: W
    • Input: QQCQR, Output: CQQ
    • Input: QQQWCCQC, Output: QWC
    I made the assumption that the machine never allows you to put in more than two quarters (after two it just spits them back out), and that if you overpay for a coke, you only get your money back with an explicit coin return call. So, for instance, QQCC gets you two cokes.


Homework Review
I had you do the following with your homeworks:
  1. On a sheet of paper separate from your homework, draw a diagram of a new machine following your model.
  2. On your howewok, in a separate area, write down the tuple representation of the machine you just drew a diagram for. Label it as "the new tuple"
  3. Pass your homework to a neighbor.
  4. Look at the homework you've been given, and draw the diagram for the "new tuple".
  5. Pass homeworks back to their author, and compare the diagram produced by your neighor with the diagram you drew on the separate sheet of paper. If they don't look the same, your formal definition of a machine in your model was not clearly written!

Pick a model
We looked at several different models proposed by students. We picked a particular model of a machine with output, which we'll call a transducer.

Formal definition of a transducer
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 }

Any regular language is ouput by some transducer
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 ...


Christopher W Brown
Last modified: Tue Nov 22 13:50:50 EST 2005