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:
“Don’t you think I’ve had enough excitement for one evening, without the additional thrill of a strange man making love to me?”
—John L. Balderston (1899–1954)
“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)
“We know then the existence and nature of the finite, because we also are finite and have extension. We know the existence of the infinite and are ignorant of its nature, because it has extension like us, but not limits like us. But we know neither the existence nor the nature of God, because he has neither extension nor limits.”
—Blaise Pascal (1623–1662)
“O! O! another stroke! that makes the third.
He stabs me to the heart against my wish.
If that be so, thy state of health is poor;
But thine arithmetic is quite correct.”
—A.E. (Alfred Edward)