Additional Properties of Finite State Transducers
- It is decidable whether the relation of a transducer T is empty.
- It is decidable whether there exists a string y such that xy for a given string x.
- It is undecidable whether two transducers are equivalent.
- 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.
Read more about this topic: Finite State Transducer
Famous quotes containing the words additional, properties, finite and/or state:
“The world will never be long without some good reason to hate the unhappy; their real faults are immediately detected, and if those are not sufficient to sink them into infamy, an additional weight of calumny will be superadded.”
—Samuel Johnson (1709–1784)
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)
“The finite is annihilated in the presence of the infinite, and becomes a pure nothing. So our spirit before God, so our justice before divine justice.”
—Blaise Pascal (1623–1662)
“To the rulers of the state then, if to any, it belongs of right to use falsehood, to deceive either enemies or their own citizens, for the good of the state: and no one else may meddle with this privilege.”
—Plato (c. 427–347 B.C.)