“Moore reduction procedure”的意思、由来-开放百科全书

词条

Moore reduction procedure

释义

See also
References

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 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 .

States that are distinguishable on the k^th partition are called k-distinguishable states. States that are in the same group on the k^th 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.

References

{{cite book|author1=Ralf Lämmel|author2=Joost Visser|author3=João Saraiva|title=Generative and Transformational Techniques in Software Engineering II: International Summer School, GTTSE 2007, Braga, Portugal, July 2-7. 2007, Revised Papers|url=https://books.google.com/books?id=PZ5uCQAAQBAJ&pg=PA483|date=8 October 2008|publisher=Springer|isbn=978-3-540-88643-3|pages=483–}}

1 : Finite automata

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

See also

References