minimal machine
minimal machine An abstract machine possessing no redundant states. To any finite-state automaton or sequential machine there corresponds a unique (up to isomorphism) minimal machine that recognizes the same language (in the case of finite automata) or has the same response function (in the case of sequential machines). This is true for infinite as well as finite state-sets.
There are two ways in which a state q may be “redundant”: it is either “inaccessible” in that there is no input string that takes the start-state to q, or else it is equivalent to another state q′ in that the subsequent behavior of the machine is the same whether it is in state q or q′. In a minimal machine all inaccessible states have been dropped and all equivalent states have been merged. There is a simple algorithm that will give the minimized version of any machine. See also Myhill equivalence, Nerode equivalence.
There are two ways in which a state q may be “redundant”: it is either “inaccessible” in that there is no input string that takes the start-state to q, or else it is equivalent to another state q′ in that the subsequent behavior of the machine is the same whether it is in state q or q′. In a minimal machine all inaccessible states have been dropped and all equivalent states have been merged. There is a simple algorithm that will give the minimized version of any machine. See also Myhill equivalence, Nerode equivalence.
More From encyclopedia.com
Sewing Machine , Background
Before 1900, women spent many of their daylight hours sewing clothes for themselves and their families by hand. Women also formed the majo… Machine , machine, arrangement of moving and stationary mechanical parts used to perform some useful work or to provide transportation. From a historical persp… Turing Machine , British mathematician Alan Turing (1912–1954) described what became known as the "Turing Machine" in his 1936 paper, "On Computable Numbers, with an… Machine Gun , Machine Guns are repeating firearms that when triggered will load and fire automatically until their ammunition is exhausted. In 1861, the U.S. Army… Typewriter , TYPEWRITER. The idea of the typewriter emerged long before the technology existed for its practical or economical production. A patent was issued in… Automation , Automation is the use of scientific and technological principles in the manufacture of machines that take over work normally done by humans. This def…
You Might Also Like
NEARBY TERMS
minimal machine