Finite State Transduction and Formal Machines

Finite state transducers (FST) are often used for computational analysis in natural languages processing research and applications such as morphology, phonology, text to speech, and data mining. It is simple, well understood mathematically, easy to implement and an efficient solution but not every problem has a finite state solution (Blackburn and Striegnitz, 2002).

Hancox (1996) defines transducer as a piece of software that maps one stream of symbols on to another stream of symbols. It means that the program translates one stream of symbols into another. Transducers are basically Mealy’s automata mentioned by Hopcroft and Ullman (1979) emphasized by Daciuk (1998). An FST is a finite state automaton that works on two tapes. It is a kind of translating machine that reads from one of the tapes and writes on the other. It can be used in different modes: translation, generation and recognition. In the generation mode, transducers write on both tapes and in the recognition mode they read from both tapes. Direction of the translation can be from left to right or right to left. Figure 2 shows the transducer that translates aS to bS and Table 1 list its different mode definition (Blackburn and Striegnitz, 2002)… [Download the complete article.]


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s