Transducers and intersection of relations

It is easier to reason about a simpler version of a NFT, one where initial and final states do not have any outputs associated with them, and where each transition outputs either nothing or just a single letter.

data NFT_List_Normalized q sigma gamma =
  NFT_List
  [q] -- the set of initial states
  [(q,Maybe sigma,Maybe gamma,q)] -- the transition relation
  [q] -- the set of final states

Even though these normalized NFTs are a restricted version of the originals, they are in fact able to compute the same relations between input and output forms. We can see this by translating them into one another. The way to eliminate special outputs on initial and final states is to expand the state set, adding one state per character output. This is shown in figure 1.

We can observe that a restricted NFT can be turned into an NFA by erasing either the inputs or the outputs on its transitions. This means that to any NFT there corresponds two NFAs; one which expresses the language of valid inputs, and the other which expresses the language of possible outputs. The NFA representing the set of possible outputs of the transducer in figure 1 is shown in figure 2.

Note that any normalized NFT can also itself be viewed as an NFA, but with an alphabet consisting of pairs of letters (of the form b:ε, for example). For example, one word in the language accepted by the NFT shown in figure 1 when we view it as an NFA is the four letter-pair string which follows: \[\langle \epsilon:x\rangle \langle a:\epsilon\rangle \langle \epsilon:y\rangle\langle \epsilon:y\rangle\] A letter-pair string accepted by a transducer¹ represents a path through the machine, and thus represents an input-output pair. The input corresponding to a letter-pair string is the string obtained by concatenating the first letters in each pair together, and the output corresponding to such a string is obtained by concatenating the second letters in each pair together. Thus the letter-pair string above corresponds to the input a and the output xyy. The crucial difference is that the input a could in principle (although not in this machine) be mapped to the output xyy in multiple different ways. For example, we might output xyy upon seeing a. Or we might erase a, and then output xyy. Or output xyy and then erase a. Or output xy, and change a to y. All of these are different ways of transducing a into xyy, and knowing that a was transduced into xyy doesn’t tell us how it happened! On the other hand, the letter-pair string gives us a complete characterization of how a is transduced into xyy: first we output x, and then a was deleted, and then we output yy.

From these basic (and hopefully obvious) facts, we can already draw some interesting conclusions. First is that, although the regular languages (the languages accepted by some NFA) are closed under intersection (i.e. if L₁ is accepted by A₁ and L₂ by A₂, then there is some NFA accepting L₁ ∩ L₂), the regular relations (the relations computed by some NFT) are not. We can argue for this in a straightforward way:

1. There is an NFT that maps aᵐbⁿ to cᵐ; it just changes each a to c and each b to ε
2. There is an NFT that maps aᵐbⁿ to cⁿ; it just changes each a to ε and each b to c

The relation computed by the first NFT is \(\{\langle a^{m}b^{n},c^{m}\rangle : m,n \in \mathbb{N}\}\), and that of the second is \(\{\langle a^{m}b^{n},c^{n}\rangle : m,n \in \mathbb{N}\}\). Their intersection relates an input aᵐbⁿ and an output cᵒ just in case m=n=o.² Can we represent this relation with an NFT? No! We can argue by reductio ad absurdum:

• towards a contradiction, assume we could; that is, that there is some NFT which maps aᵐbᵐ to cᵐ, and nothing else to anything else
• Since this is an NFT, there is an NFA describing its set of well-formed inputs, aᵐbᵐ
• This is a contradiction, because aᵐbᵐ is not a regular language!

This is great! We’ve seen that the relations computed by NFTs are not closed under intersection! But wait! We’ve also seen that NFTs can be viewed as NFAs over letter-pair alphabets, and we know that the languages accepted by NFAs are closed under intersection! How can both of these things be true at the same time?!?!?! We have already seen the answer above: letter-pair strings contain strictly more information about the structure of the machine than do input-output pairs. When we intersect letter-pair languages, we are determining whether an input was mapped to an output in the same way in both machines. When we intersect relations, we are determining whether an input was mapped to an output in both relations, irrespective of how. Let us consider for a moment the letter-pair languages of the NFTs described above (mapping aᵐbⁿ to cᵐ and cⁿ respectively). An input aabb in both machines is transduced to cc, but these machines perform this transduction in different ways. The letter-pair sequence corresponding to this transduction in the first machine is \(\langle a:c\rangle\langle a:c\rangle\langle b:\epsilon\rangle\langle b:\epsilon\rangle\) - it maps each a to a c, and deletes each b. The letter-pair sequence corresponding to this same transduction in the second machine is \(\langle a:\epsilon\rangle\langle a:\epsilon\rangle\langle b:c\rangle\langle b:c\rangle\) - it deletes each a, and then maps each b to a c. A little thought will make it plausible that the letter-pair languages of these transducers have nothing in common, and so their intersection is the empty letter-pair language, which is of course representable as a transducer (one which is not defined on any input).