Definition
A finite-state machine (FSM) or finite-state automaton, 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. For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.
Related concepts
Abstract machineAbstract state machineAddison-WesleyAlfred V. AhoAlgebraic path problemAlphabet (computer science)Alternating finite automatonAperiodic finite state automatonApplication-specific integrated circuitAsynchronous circuitAutomata-based programmingAutomata theoryBinary numeral systemBiologyBoolean algebraBoolean circuitCapacitorChomsky hierarchyChristos H. PapadimitriouChristos PapadimitriouCircuit diagramCircuit minimization for Boolean functionsCombination lockCombinational logicCommunicating finite-state machineCompilerCompilersComplex programmable logic deviceComputational linguisticsComputer architectureComputer hardwareComputer memoryComputer scienceContext-free grammarContext-free languageContext-sensitive grammarContext-sensitive languageControl systemControl tableControl theoryDEVSDFA minimizationDavid HarelDecider (Turing machine)Decision tableDerick WoodDeterministic acyclic finite state automatonDeterministic context-free grammarDeterministic context-free languageDeterministic finite automatonDeterministic pushdown automatonDigital audioDigital cinematographyDigital circuitDigital electronicsDigital photographyDigital radioDigital signalDigital signal (signal processing)Digital signal processingDigital televisionDigital videoDirected graphElectrical engineeringElectronic circuitElectronic componentElectronic literatureElectronics designElevatorEmbedded pushdown automatonEmitter-coupled logicEmpty stringErasable programmable logic deviceEvent-driven finite-state machineField-programmable gate arrayField-programmable object arrayFinite-state machineFinite-state transducerFinite Automata (band)Finite languageFlip-flop (electronics)Formal equivalence checkingFormal grammarFormal languageGate equivalentGeneralized nondeterministic finite automatonGeneric Array LogicHardware accelerationHardware description languageHarry R. LewisHidden Markov modelHierarchical state machineHigh-level synthesisHybrid integrated circuitITUImplication tableIndexed grammarIndexed languageInductorInput (computer science)Integrated circuitIntroduction to Automata Theory, Languages, and ComputationJeffrey D. UllmanJeffrey UllmanJohn HopcroftLexical analysisLinear bounded automatonLinear context-free rewriting languageLinear context-free rewriting systemLinear timeLinguisticsLogicLogic gateLogic in computer scienceLogic synthesisMacrocell arrayMarkov chainMathematicMealy machineMemory cell (computing)Metastability (electronics)Mixed-signal integrated circuitModel of computationMoore machineNational Institute of Standards and TechnologyNested stack automatonNested wordNetwork protocolNode (graph theory)Non-recursive grammarNondeterministic finite automatonPTIMEPartial functionPetri netPhilosophyPlace and routePlacement (electronic design automation)Powerset constructionPrinted circuit boardPrinted electronicsProcessor registerProgrammable Array LogicProgrammable logic arrayProgrammable logic controllerProgrammable logic deviceProper subsetPushdown automatonQuantum finite automatonRajeev MotwaniRange concatenation grammarsRange concatenation languageRavi SethiRecursive languageRecursively enumerable languageRegister-transfer levelRegular grammarRegular languageRelayResistorRouting (electronic design automation)Runt pulseSCXMLSFSM (company)SemiautomatonSemigroup actionSemiringSequential logicSextupleShortest path problemSoftware engineeringSpecification and Description LanguageStar-free languageState-transition tableState (computer science)State diagramState encoding for low powerState machine (disambiguation)State patternString (computer science)Subshifts of finite typeSwitching circuit theorySynchronizing wordSynchronous circuitTelephonyTensor Processing UnitTheory of computationThread automatonThree-dimensional integrated circuitToken coinTraffic lightTransaction-level modelingTransformation semigroupTransistorTransistor–transistor logicTransition systemTree-adjoining grammarTree automatonTree stack automatonTruth tableTupleTuring machineTurnstileUML state machineUnified Modeling LanguageUnrestricted grammarVending machineVideo game programmingVirtual finite-state machineVirtual finite state machineΕ
16 concepts already in your glossary