Search code examples
relationstate-machinetransducer

Finite-state transducer that computes the relation

From http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-twoli1.html#30007-23021r2.2.4:

Let M = <Q, Σ, Δ, δ, q0, F> be the deterministic finite-state transducer whose transition diagram is given in Figure 2.E.2.

Figure 2.E.2

For each of the following relations find a finite-state transducer that computes the relation.

a. { (x, y) | x is in L(M), and y is in Δ* }.
b. { (x, y) | x is in L(M), y is in Δ*, and (x, y) is not in R(M) }.

Yes, this is HW, but I have been struggling with these questions and could at least use pointers. If you want to create your own c. and/or d. examples just to show me HOW to do it rather than lead me to the answers for a. and b. then obviously I'm fine with that.

Thanks in advance!

Solution

  • Since you don't indicate what progress you've made so far, I'm going to assume that you've made no progress at all, and will give overall guidance for how you can approach this sort of problem.

    • First of all, examine the transition diagram. Do you understand what all the notations mean? Note that the transducer is described as deterministic. Do you understand what that means? Convince yourself that the transducer depicted in the transition diagram is, in fact, deterministic. Trace through it; try to get a sense for what inputs are accepted by the transducer, and what outputs it gives.
    • Next, figure out what L(M), Δ, and R(M) are for this transducer, since the questions refer to them. Do you know what those notations mean?
    • Do you know what it means for a transducer to compute a certain relation? Do you understand the { (x, y) | ... } notation for describing the relation?
    • Can you modify the transition diagram to eliminate the ε/0 transition and merge it into adjacent transitions (which then might output multiple symbols at a single transition)? (This can help, IMHO, with creating other transducers that accept the same input language. More so with part b, in this case, than part a.)
    • Describe for yourself the transducers you need to create, in a way that's independent of the original transducer. Will these transducers be deterministic?
    • Create the transition diagrams for these transducers.