structure of the transducer (the twins property). Weight pushing for the weighted case. Minimization for the weighted case. Removal of epsilon-transitions. Additional properties of finite-state transducers It is decidable whether the relation [T] of a transducer T is empty. It is decidable whether there exists a string y such that x[T]y for a given string x. It is undecidable whether two transducers are equivalent. Equivalence is however decidable in the special case where the relation [T] of a transducer T is a (partial) function. If one defines the alphabet of labels , finite-state transducers are isomorphic to NDFA over the alphabet , and may therefore be determinized (turned into deterministic finite automata over the alphabet ) and subsequently minimized so that they have the minimum number of states. Applications FSTs are used in the lexical analysis phase of compilers to associate semantic value with the discovered tokens. Context-sensitive rewriting rules of the form a → b / c _ d, used in linguistics to model phonological rules and sound change, are computationally equivalent to finite-state transducers, provided that application is nonrecursive, i.e. the rule is not allowed to rewrite the same substring twice. Weighted FSTs found applications in natural language processing, including machine translation, and in machine learning. An implementation for part-of-speech tagging can be found as one component of the OpenGrm library. See also Mealy machine Moore machine Morphological dictionary foma (software) Tree transducer Notes References External links OpenFst, an open-source library for FST operations. Finite State Morphology--The Book XFST/ LEXC, a description of Xerox's implementation of finite-state transducers intended for linguistic applications. The Helsinki open source implementation and extension of the Xerox fst FOMA, an open-source implementation of most of the capabilities of the Xerox XFST/ LEXC implementation. Stuttgart Finite State Transducer Tools, another open-source FST toolkit java FST Framework, an open-source java FST Framework capable of handling OpenFst text format. Vcsn, an open-source platform (C++ & IPython) platform for weighted automata and rational expressions. Further reading . Free PDF version Finite automata