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:
“When I turned into a parent, I experienced a real and total personality change that slowly shifted back to the “normal” me, yet has not completely vanished. I believe the two levels are now superimposed, with an additional sprinkling of mortality intimations.”
—Sonia Taitz (20th century)
“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)
“For it is only the finite that has wrought and suffered; the infinite lies stretched in smiling repose.”
—Ralph Waldo Emerson (1803–1882)
“The man of large and conspicuous public service in civil life must be content without the Presidency. Still more, the availability of a popular man in a doubtful State will secure him the prize in a close contest against the first statesman of the country whose State is safe.”
—Rutherford Birchard Hayes (1822–1893)