Editing Finite-state transducer (section)

==Additional properties of finite-state transducers==

* It is [[Decidability (logic)|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 problem|undecidable]] whether two transducers are equivalent.<ref>{{harvnb|Griffiths|1968}}</ref> 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 <math>L=(\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\})</math>, finite-state transducers are isomorphic to [[nondeterministic finite automata|NDFA]] over the alphabet <math>L</math>, and may therefore be determinized (turned into [[deterministic finite automaton|deterministic finite automata]] over the alphabet <math>L=[(\Sigma\cup\{\epsilon\}) \times \Gamma] \cup [\Sigma \times (\Gamma\cup\{\epsilon\})]</math>) and subsequently minimized so that they have the minimum number of states.{{Citation needed|date=September 2008}}