FSTs are used for Natural Language Processing (NLP). To understand the function of an FST, let us understand a Finite State Machine (FSM) first. An FSM is an abstract mathematical model of computation that is capable of storing a status or state and changing this state on the basis of the input. FSMs can be applied to various electronic modeling, engineering, and NLP problems. An FSM is represented as a set of nodes containing the various states of a system and labeled edges between these nodes. Here the edges represent transitions from one state to another and the labels represent the conditions on these transitions. A stream of input can be then processed by the FSM causing a number of state transitions.

The following diagram is an example of an FSM that describes some of the states of our day-to-day life:

Here Eat, Sleep, and Work are the states in which a person will be. Bored, Tired, and Hungry are the edges showing the conditions under which transitions...