Finite-state machine
A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. A deterministic finite-state machine can be constructed equivalent to any non-deterministic one.
- Comment
- enA finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. A deterministic finite-state machine can be constructed equivalent to any non-deterministic one.
- Cs1Dates
- eny
- Date
- enJanuary 2020
- 19 November 2008
- Depiction
- Has abstract
- enA finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. A deterministic finite-state machine can be constructed equivalent to any non-deterministic one. 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, whose sequence of stops is determined by the floors requested by riders, traffic lights, which change sequence when cars are waiting, and combination locks, which require the input of a sequence of numbers in the proper order. The finite-state machine has less computational power than some other models of computation such as the Turing machine. The computational power distinction means there are computational tasks that a Turing machine can do but an FSM cannot. This is because an FSM's memory is limited by the number of states it has. A finite-state machine has the same computational power as a Turing machine that is restricted such that its head may only perform "read" operations, and always has to move from left to right. FSMs are studied in the more general field of automata theory.
- Hypernym
- Model
- Is primary topic of
- Finite-state machine
- Label
- enFinite-state machine
- Link from a Wikipage to an external page
- research.microsoft.com/~gurevich/Opera/141.pdf
- blogs.itemis.com/en/a-brief-overview-of-state-machine-types
- philpapers.org/archive/CARTOF.pdf
- archive.org/details/computabilitylog0000bool_r8y9
- archive.org/details/computationfinit0000mins%7C
- archive.org/details/digitalnetworksc00boot
- archive.org/details/discretemathemat0000bobr
- www.itu.int/rec/T-REC-Z.100-200711-I/en
- web.archive.org/web/20171211180457/http:/foldoc.org/finite+state+machine
- archive.org/details/finitemathematic0000keme_h5g0%7C
- web.archive.org/web/20181013023517/https:/xlinux.nist.gov/dads/HTML/finiteStateMachine.html
- www.troyworks.com/cogs/
- archive.today/20121202054532/http:/blog.manuvra.com/modeling-a-simple-ai-behavior-using-a-finite-state-machine/
- web.archive.org/web/20081119071252/http:/www.troyworks.com/cogs/
- www.state-machine.com/psicc/index.php
- www.state-machine.com/psicc2/index.php
- Link from a Wikipage to another Wikipage
- Abstract machine
- Abstract state machine
- Algebraic path problem
- Alphabet (computer science)
- Alternating finite automaton
- Automata-based programming
- Automata theory
- Binary numeral system
- Biology
- Cambridge University Press
- Category:Finite automata
- Combinational logic
- Combination lock
- Communicating finite-state machine
- Compiler
- Compilers
- Computational linguistics
- Computer memory
- Computer science
- Context-free grammar
- Control system
- Control table
- Control theory
- David Harel
- Decision table
- Deterministic finite automaton
- DEVS
- DFA minimization
- Digital circuit
- Digital electronics
- Directed graph
- Electrical engineering
- Elevator
- Empty string
- Event-driven finite-state machine
- File:4 bit counter.svg
- File:DFAexample.svg
- File:Finite state machine example with comments.svg
- File:Fsm mealy model door control.svg
- File:Fsm Moore model door control.svg
- File:Fsm parsing word nice.svg
- File:SdlStateMachine.png
- File:Torniqueterevolution.jpg
- File:Turnstile state machine colored.svg
- File:UML state machine Fig5.png
- Finite-state transducer
- Flip-flop (electronics)
- Formal language
- Generalized nondeterministic finite automaton
- Hidden Markov model
- Implication table
- Input (computer science)
- ITU
- Lexical analysis
- Linear time
- Linguistics
- Logic
- Logic gate
- Markov chain
- Mathematic
- Mealy machine
- Model of computation
- Moore machine
- Network protocol
- Node (graph theory)
- Nondeterministic finite automaton
- Partial function
- Petri net
- Philosophy
- Powerset construction
- Processor register
- Programmable logic controller
- Programmable logic device
- Pushdown automaton
- Quantum finite automaton
- Regular language
- Relay
- Richards controller
- SCXML
- Semiautomaton
- Semigroup action
- Semiring
- Sequential logic
- Sextuple
- Shortest path problem
- Software engineering
- Specification and Description Language
- State (computer science)
- State diagram
- State encoding for low power
- State pattern
- State-transition table
- String (computer science)
- Subshifts of finite type
- Synchronizing word
- Theory of computation
- Token coin
- Traffic light
- Transformation semigroup
- Transition system
- Tree automaton
- Truth table
- Tuple
- Turing machine
- Turnstile
- UML state machine
- Unified Modeling Language
- Vending machine
- Video game programming
- Virtual finite state machine
- Virtual finite-state machine
- Ε
- SameAs
- Äärellinen automaatti
- Ändlig automat
- Automa a stat finii
- Automa a stati finiti
- Autómata finito
- Autómata finito
- Automata finitu
- Automate fini
- Automat finit
- Autòmat finit
- Automat skończony
- Baigtinis automatas
- Eindigetoestandsautomaat
- Endelig tilstandsmaskin
- Endlicher Automat
- Finia aŭtomato
- Finite-state machine
- Galīgs automāts
- hq5C
- Konačni automat
- Konačni automat
- Konačni automat
- Konečný automat
- Konečný automat
- Lõplik olekumasin
- m.02ykc
- Máquina de estados finita
- Máy trạng thái hữu hạn
- Q176452
- Sonlu durum makinesi
- Коначан аутомат
- Конечен автомат
- Конечный автомат
- Краен автомат
- Скінченний автомат
- Վերջավոր ավտոմատ
- אוטומט סופי
- آلة محدودة الحالات
- ماشین حالات متناهی
- เครื่องสถานะจำกัด
- სასრული მანქანა
- 有限オートマトン
- 有限状态机
- 유한 상태 기계
- Subject
- Category:Finite automata
- Thumbnail
- Url
- https://web.archive.org/web/20081119071252/http:/www.troyworks.com/cogs/
- WasDerivedFrom
- Finite-state machine?oldid=1123320568&ns=0
- WikiPageLength
- 41948
- Wikipage page ID
- 10931
- Wikipage revision ID
- 1123320568
- WikiPageUsesTemplate
- Template:Automata theory
- Template:Citation needed
- Template:Cite book
- Template:Cite journal
- Template:Colend
- Template:Cols
- Template:Commons category
- Template:Curlie
- Template:Diagonal split header
- Template:Digital systems
- Template:Explain
- Template:Formal languages and grammars
- Template:Hatnote
- Template:ISBN
- Template:Main
- Template:Redirect
- Template:Reflist
- Template:Rp
- Template:Short description
- Template:Technical statement
- Template:Use dmy dates
- Template:Webarchive
