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

T1 and T2

Composition of T1 and T2

The states of the composition T are pairs of a T1 state and a T2 state. T satisfies the following conditions:

1. its initial state is the pair of the initial state of T1 and the initial state of T2
2. Its final states are pairs of a final state of T1 and a final state of T2
3. There is a transition t from (q1, q2) to (r1, r2) for each pair of transitions T1 from q1 to r1 and T2 from q2 to r2 such that the output label of T1 matches the input label of T2. The transition T takes its input label from T1, its output label from T2, and its weight is the combination of the weights of T1 and T2 done with the same operation that combines weights along a path.

Since there are no weights we can ignore this. Above was picked up exactly from a following beautiful paper. Link here