How to perform FST (Finite State Transducer) composition

Question

Consider the following FSTs :

T1 

0 1 a : b
0 2 b : b
2 3 b : b
0 0 a : a
1 3 b : a

T2

0 1 b : a
1 2 b : a
1 1 a : d
1 2 a : c

How do I perform the composition operation on these two FSTs (i.e. T1 o T2) I saw some algorithms but couldn't understand much. If anyone could explain it in a easy way it would be a major help.

Please note that this is NOT a homework. The example is taken from the lecture slides where the solution is given but I couldn't figure out how to get to it.

Answer 1

Since you didn't specify the input format, I'm assuming that 0 is the initial state, any integers that appear in the second column but not the first are accepting states (3 for T1 and 2 for T2), and each row is an element of the transition relation, giving the the previous state, the next state, the input letter and the output letter.

Any operation on FSTs needs to produce a new FST, so we need states, an input alphabet, an output alphabet, initial states, final states and a transition relation (the specifications of the FSTs A, B and W below are given in this order). Suppose our FSTs are:

A = (Q, Σ, Γ, Q0, QF, α)
B = (P, Γ, Δ, P0, PF, β)

and we want to find

W = (R, Σ, Δ, R0, RF, ω) = A ∘ B

Note that we don't need to determine the alphabets of W; the definition of composition does that.

Imagine running A and B in series, with A's output tape fed as B's input tape. The state of the combined FST is simply the combined states of A and B. In other words, the states of the composition are in the cross product of the states of the individual FSTs.

R = Q × P

In your example, the states of W would be pairs of integers:

R = {(0,0), (0,1), ... (3, 2)}

though we could renumber these and get (for example):

R = {00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32}

Similarly, initial and accepting states of the composed FST are the cross products of those in the component FSTs. In particular, R accepts a string iff A and B both accept the string.

R0 = Q0 × P0
RF = QF × PF

In the example, R₀ = {00} and R_F = {32}.

All that remains is to determine the transition relationship ω. For this, combine each transition rule for A with every transition rule for B that might apply. That is, combine each transition rule of A (qi, σ) → (qj, γ) with every rule of B that has a "γ" as the input character.

ω = { ((qi,ph), σ) → ((qj, pk), δ) : (qi, σ) → (qj, γ) ∈ α, 
                                     (ph, γ) → (pk, δ) ∈ β}

In the example, this means combining (e.g.) 0 1 a : b of T1 with 0 1 b : a and 1 2 b : a of T2 to get:

00 11 a : a
01 12 a : a

Similarly, you'd combine 0 2 b : b of T1 with those same 0 1 b : a and 1 2 b : a of T2, 0 0 a : a of T1 with 1 1 a : d and 1 2 a : c of T2 &c.

Note that you might have unreachable states (those that never appear as a "next" state) and transitions that will never occur (those from unreachable states). As an optimization step, you can remove those states and transitions. However, leaving them in will not affect the correctness of the construction; it's simply an optimization.

Answer 2

If you are more amenable to graphical explanations, the following set of slides provides incremental, graphical examples of the composition algorithm in practice, and also includes discussion of epsilon transitions in the component transducers. Epsilon transitions complicate the composition process, and the algorithm described in outis answer may not generate the correct result in this case, depending on the semiring being used.

See slides 10~35 for some graphical examples:

http://www.gavo.t.u-tokyo.ac.jp/~novakj/wfst-algorithms.pdf