![]() In order to fully understand conceptually a finite-state machine, consider an analogy to an elevator:Īn elevator is a mechanism that does not remember all previous requests for service but the current floor, the direction of motion (up or down) and the collection of not-yet satisfied requests for services. Finite-machines are also used for purposes aside from general computations, such as to recognize regular languages. Its main application is in mathematical problem analysis. This mathematical model of a machine can only reach a finite number of states and transitions between these states. Therefore, it can be seen as a function which maps an ordered sequence of input events into a corresponding sequence, or set, of output events.įinite-state machines are ideal computation models for a small amount of memory, and do not maintain memory. The state transition function takes the current state and an input event and returns the new set of output events and the next state. FSMs are abstract machines, consisting of a set of states (set Q), set of input events (set I), a set of output events (set Z) and a state transition function. While the Mealy machine determines its outputs through the current state and the input, the Moore machine's output is based upon the current state alone.Īn automaton in which the state set Q contains only a finite number of elements is called a finite-state machine (FSM). The finite-state machines, the Mealy machine and the Moore machine, are named in recognition of their work. Moore, generalized the theory to much more powerful machines in separate papers, published in 1955-56. Their paper, entitled, "A Logical Calculus Immanent in Nervous Activity", made significant contributions to the study of neural network theory, theory of automata, the theory of computation and cybernetics. Warren McCulloch and Walter Pitts, two neurophysiologists, were the first to present a description of finite automata in 1943. They all shared a common interest: to model the human thought process, whether in the brain or in a computer. The first people to consider the concept of a finite-state machine included a team of biologists, psychologists, mathematicians, engineers and some of the first computer scientists. The exciting history of how finite automata became a branch of computer science illustrates its wide range of applications. A Turing machine is a finite-state machine yet the inverse is not true. The focus of this project is on the finite-state machine and the Turing machine. The families of automata above can be interpreted in a hierarchal form, where the finite-state machine is the simplest automata and the Turing machine is the most complex. There are four major families of automaton : ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |