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)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)
“God is a being of transcendent and unlimited perfections: his nature therefore is incomprehensible to finite spirits.”
—George Berkeley (1685–1753)
“From this elevation, just on the skirts of the clouds, we could overlook the country, west and south, for a hundred miles. There it was, the State of Maine, which we had seen on the map, but not much like that,—immeasurable forest for the sun to shine on, the eastern stuff we hear of in Massachusetts. No clearing, no house. It did not look as if a solitary traveler had cut so much as a walking-stick there.”
—Henry David Thoreau (1817–1862)