Moore reduction procedure
- Moore reduction procedure
-
In computer science, the Moore reduction procedure is a method used for DFA minimization.
The concept is to start assuming that every state may be able to combine with every other state, then separate distinguishable states into separate groups called equivalence partitions. When no more equivalence partitions contain distinguishable states, the states remaining in the same group as other states are can be combined. Equivalence partitions are numbered by the number of steps it took to get to that point. The 0th partition contains all the states in one group, the 1st partition contains states grouped by their outputs only. Every partition from then on has groupings that are based on which group from the previous partition those states' next state fell under. The procedure is complete when partition n is the same as partition n + 1.
States that are distinguishable on the kth partition are called k-distinguishable states. States that are in the same group on the kth partition are called k-equivalent. Note that states that are k-equivalent at one point are not necessarily equivalent states, as they may be separated into separate groups in a higher partition.
The procedure is as follows:
- separate states into groups that have the same immediate output for the same current input,
- distinguish states whose next state(s) are in different groups.
- regroup the states and repeat the above step until no more states are distinguishable.
See also
Wikimedia Foundation.
2010.
Look at other dictionaries:
Moore–Penrose pseudoinverse — In mathematics, and in particular linear algebra, a pseudoinverse A+ of a matrix A is a generalization of the inverse matrix.[1] The most widely known type of matrix pseudoinverse is the Moore–Penrose pseudoinverse, which was independently… … Wikipedia
Clitoral hood reduction — Clitoral hood reduction: the pre operative aspects of clitoral prepuce and labia minora hypertrophy (left), and the post operative aspects of the reduced prepuce and labia minora. (right) Clitoral hood reduction is an elective plastic surgery… … Wikipedia
Finite state machine — A finite state machine (FSM) or finite state automaton (plural: automata ) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an… … Wikipedia
Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… … Wikipedia
Implication table — An implication table is a tool used to facilitate the minimization of states in a state machine. The concept is to start assuming that every state may be able to combine with every other state, then eliminate combinations that are not possible.… … Wikipedia
United States — a republic in the N Western Hemisphere comprising 48 conterminous states, the District of Columbia, and Alaska in North America, and Hawaii in the N Pacific. 267,954,767; conterminous United States, 3,022,387 sq. mi. (7,827,982 sq. km); with… … Universalium
Labioplastik — Verkleinerung der inneren Schamlippen: vor (links) und nach (rechts) der Operation Als Labioplastik (synonym: Labioplastie, Schamlippenplastik, Schamlippenkorrektur) werden Operationen der Plastischen Chirurgie zur Reduzierung, Modifizierung,… … Deutsch Wikipedia
Economic Affairs — ▪ 2006 Introduction In 2005 rising U.S. deficits, tight monetary policies, and higher oil prices triggered by hurricane damage in the Gulf of Mexico were moderating influences on the world economy and on U.S. stock markets, but some other… … Universalium
Algorithmic efficiency — In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or… … Wikipedia
Pure tone audiometry — (PTA) is the key hearing test used to identify hearing threshold levels of an individual, enabling determination of the degree, type and configuration of a hearing loss. Thus, providing the basis for diagnosis and management. PTA is a subjective … Wikipedia
