|
A finite-state machine (FSM) or finite-state automaton (plural: ''automata''), or simply a state machine, is a mathematical model of computation used to design both computer programs and sequential logic circuits. It is conceived as an abstract machine that can be in one of a finite number of ''states''. The machine is in only one state at a time; the state it is in at any given time is called the ''current state''. It can change from one state to another when initiated by a triggering event or condition; this is called a ''transition''. A particular FSM is defined by a list of its states, and the triggering condition for each transition. The behavior of state machines can be observed in many devices in modern society that perform a predetermined sequence of actions depending on a sequence of events with which they are presented. Simple examples are vending machines, which dispense products when the proper combination of coins is deposited, elevators, which drop riders off at upper floors before going down, traffic lights, which change sequence when cars are waiting, and combination locks, which require the input of combination numbers in the proper order. Finite-state machines can model a large number of problems, among which are electronic design automation, communication protocol design, language parsing and other engineering applications. In biology and artificial intelligence research, state machines or hierarchies of state machines have been used to describe neurological systems. In linguistics, they are used to describe simple parts of the grammars of natural languages. Considered as an abstract model of computation, the finite state machine is weak; it has less computational power than some other models of computation such as the Turing machine. That is, there are tasks that no FSM can do, but some Turing machines can. This is because the FSM memory is limited by the number of states. FSMs are studied in the more general field of automata theory. == Example: coin-operated turnstile == An example of a very simple mechanism that can be modeled by a state machine is a turnstile. A turnstile, used to control access to subways and amusement park rides, is a gate with three rotating arms at waist height, one across the entryway. Initially the arms are locked, blocking the entry, preventing patrons from passing through. Depositing a coin or token in a slot on the turnstile unlocks the arms, allowing a single customer to push through. After the customer passes through, the arms are locked again until another coin is inserted. Considered as a state machine, the turnstile has two states: ''Locked'' and ''Unlocked''.〔 There are two inputs that affect its state: putting a coin in the slot (''coin'') and pushing the arm (''push''). In the locked state, pushing on the arm has no effect; no matter how many times the input ''push'' is given, it stays in the locked state. Putting a coin in – that is, giving the machine a ''coin'' input – shifts the state from ''Locked'' to ''Unlocked''. In the unlocked state, putting additional coins in has no effect; that is, giving additional ''coin'' inputs does not change the state. However, a customer pushing through the arms, giving a ''push'' input, shifts the state back to ''Locked''. The turnstile state machine can be represented by a state transition table, showing for each state the new state and the output (action) resulting from each input It can also be represented by a directed graph called a state diagram ''(above)''. Each of the states is represented by a node (''circle''). Edges (''arrows'') show the transitions from one state to another. Each arrow is labeled with the input that triggers that transition. Inputs that don't cause a change of state (such as a ''coin'' input in the ''Unlocked'' state) are represented by a circular arrow returning to the original state. The arrow into the ''Locked'' node from the black dot indicates it is the initial state. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Finite-state machine」の詳細全文を読む スポンサード リンク
|