Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

Finite-state machine

Index 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. [1]

97 relations: Abstract machine, Abstract State Machine Language, Abstract state machines, Addison-Wesley, Alphabet (formal languages), Artificial intelligence, Automata theory, Automata-based programming, Behavior selection algorithm, Binary number, Biology, Cambridge University Press, Combination lock, Combinational logic, Communicating finite-state machine, Communication protocol, Compiler, Compilers: Principles, Techniques, and Tools, Computational linguistics, Computer memory, Computer science, Control system, Control table, Decision table, Deterministic finite automaton, DEVS, Digital electronics, Directed graph, Electrical engineering, Elevator, Empty string, Event-driven finite-state machine, Extended finite-state machine, Finite state machine with datapath, Finite-state transducer, Flip-flop (electronics), Generalized nondeterministic finite automaton, Hamburg University of Applied Sciences, Hidden Markov model, Implication table, Input (computer science), International Telecommunication Union, Introduction to Automata Theory, Languages, and Computation, Lexical analysis, Linguistics, Logic, Logic gate, Markov chain, Mathematics, Mealy machine, ..., Model of computation, Moore machine, Moore reduction procedure, National Institute of Standards and Technology, Nondeterministic finite automaton, Partial function, Petri net, Philosophy, Powerset construction, Processor register, Programmable logic controller, Programmable logic device, Pushdown automaton, Quantum finite automata, Recursively enumerable language, Regular language, Relay, Richards controller, SCXML, Semiautomaton, Semiring, Sequential logic, 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), Subshift of finite type, Theory of computation, Token coin, Traffic light, Transition system, Tree automaton, Truth table, Tuple, Turing machine, Turnstile, UML state machine, Unified Modeling Language, Vending machine, Vertex (graph theory), Virtual finite-state machine, YAKINDU Statechart Tools. Expand index (47 more) »

Abstract machine

An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory.

New!!: Finite-state machine and Abstract machine · See more »

Abstract State Machine Language

Abstract State Machine Language (AsmL) is a programming language based on the Abstract State Machines formal method and developed by Microsoft.

New!!: Finite-state machine and Abstract State Machine Language · See more »

Abstract state machines

In computer science, an abstract state machine (ASM) is a state machine operating on states that are arbitrary data structures (structure in the sense of mathematical logic, that is a nonempty set together with a number of functions (operations) and relations over the set).

New!!: Finite-state machine and Abstract state machines · See more »


Addison-Wesley is a publisher of textbooks and computer literature.

New!!: Finite-state machine and Addison-Wesley · See more »

Alphabet (formal languages)

In formal language theory, a string is defined as a finite sequence of members of an underlying base set; this set is called the alphabet of a string or collection of strings.

New!!: Finite-state machine and Alphabet (formal languages) · See more »

Artificial intelligence

Artificial intelligence (AI, also machine intelligence, MI) is intelligence demonstrated by machines, in contrast to the natural intelligence (NI) displayed by humans and other animals.

New!!: Finite-state machine and Artificial intelligence · See more »

Automata theory

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them.

New!!: Finite-state machine and Automata theory · See more »

Automata-based programming

Automata-based programming is a programming paradigm in which the program or part of it is thought of as a model of a finite state machine (FSM) or any other (often more complicated) formal automaton (see automata theory).

New!!: Finite-state machine and Automata-based programming · See more »

Behavior selection algorithm

In artificial intelligence, a behavior selection algorithm, or action selection algorithm, is an algorithm that selects appropriate behaviors or actions for one or more intelligent agents.

New!!: Finite-state machine and Behavior selection algorithm · See more »

Binary number

In mathematics and digital electronics, a binary number is a number expressed in the base-2 numeral system or binary numeral system, which uses only two symbols: typically 0 (zero) and 1 (one).

New!!: Finite-state machine and Binary number · See more »


Biology is the natural science that studies life and living organisms, including their physical structure, chemical composition, function, development and evolution.

New!!: Finite-state machine and Biology · See more »

Cambridge University Press

Cambridge University Press (CUP) is the publishing business of the University of Cambridge.

New!!: Finite-state machine and Cambridge University Press · See more »

Combination lock

A combination lock is a type of locking device in which a sequence of symbols, usually numbers, is used to open the lock.

New!!: Finite-state machine and Combination lock · See more »

Combinational logic

In digital circuit theory, combinational logic (sometimes also referred to as time-independent logic) is a type of digital logic which is implemented by Boolean circuits, where the output is a pure function of the present input only.

New!!: Finite-state machine and Combinational logic · See more »

Communicating finite-state machine

In computer science, a communicating finite-state machine is a finite state machine labeled with "receive" and "send" operations over some alphabet of channels.

New!!: Finite-state machine and Communicating finite-state machine · See more »

Communication protocol

In telecommunication, a communication protocol is a system of rules that allow two or more entities of a communications system to transmit information via any kind of variation of a physical quantity.

New!!: Finite-state machine and Communication protocol · See more »


A compiler is computer software that transforms computer code written in one programming language (the source language) into another programming language (the target language).

New!!: Finite-state machine and Compiler · See more »

Compilers: Principles, Techniques, and Tools

Compilers: Principles, Techniques, and Tools is a computer science textbook by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman about compiler construction.

New!!: Finite-state machine and Compilers: Principles, Techniques, and Tools · See more »

Computational linguistics

Computational linguistics is an interdisciplinary field concerned with the statistical or rule-based modeling of natural language from a computational perspective, as well as the study of appropriate computational approaches to linguistic questions.

New!!: Finite-state machine and Computational linguistics · See more »

Computer memory

In computing, memory refers to the computer hardware integrated circuits that store information for immediate use in a computer; it is synonymous with the term "primary storage".

New!!: Finite-state machine and Computer memory · See more »

Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

New!!: Finite-state machine and Computer science · See more »

Control system

A control system manages, commands, directs, or regulates the behavior of other devices or systems using control loops.

New!!: Finite-state machine and Control system · See more »

Control table

Control tables are tables that control the control flow or play a major part in program control.

New!!: Finite-state machine and Control table · See more »

Decision table

Decision tables are a concise visual representation for specifying which actions to perform depending on given conditions.

New!!: Finite-state machine and Decision table · See more »

Deterministic finite automaton

In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as a deterministic finite acceptor (DFA) and a deterministic finite state machine (DFSM) or a deterministic finite state automaton (DFSA)—is a finite-state machine that accepts or rejects strings of symbols and only produces a unique computation (or run) of the automaton for each input string.

New!!: Finite-state machine and Deterministic finite automaton · See more »


DEVS abbreviating Discrete Event System Specification is a modular and hierarchical formalism for modeling and analyzing general systems that can be discrete event systems which might be described by state transition tables, and continuous state systems which might be described by differential equations, and hybrid continuous state and discrete event systems.

New!!: Finite-state machine and DEVS · See more »

Digital electronics

Digital electronics or digital (electronic) circuits are electronics that operate on digital signals.

New!!: Finite-state machine and Digital electronics · See more »

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is a set of vertices connected by edges, where the edges have a direction associated with them.

New!!: Finite-state machine and Directed graph · See more »

Electrical engineering

Electrical engineering is a professional engineering discipline that generally deals with the study and application of electricity, electronics, and electromagnetism.

New!!: Finite-state machine and Electrical engineering · See more »


An elevator (US and Canada) or lift (UK, Australia, Ireland, New Zealand, and South Africa, Nigeria) is a type of vertical transportation that moves people or goods between floors (levels, decks) of a building, vessel, or other structure.

New!!: Finite-state machine and Elevator · See more »

Empty string

In formal language theory, the empty string, or empty word is the unique string of length zero.

New!!: Finite-state machine and Empty string · See more »

Event-driven finite-state machine

In computation, a finite-state machine (FSM) is event driven if the transition from one state to another is triggered by an event or a message.

New!!: Finite-state machine and Event-driven finite-state machine · See more »

Extended finite-state machine

In a conventional finite state machine, the transition is associated with a set of input Boolean conditions and a set of output Boolean functions.

New!!: Finite-state machine and Extended finite-state machine · See more »

Finite state machine with datapath

A Finite State Machine with Datapath (FSMD) is a mathematical abstraction that is sometimes used to design digital logic or computer programs.

New!!: Finite-state machine and Finite state machine with datapath · See more »

Finite-state transducer

A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape.

New!!: Finite-state machine and Finite-state transducer · See more »

Flip-flop (electronics)

In electronics, a flip-flop or latch is a circuit that has two stable states and can be used to store state information.

New!!: Finite-state machine and Flip-flop (electronics) · See more »

Generalized nondeterministic finite automaton

In the theory of computation, a generalized nondeterministic finite automaton (GNFA), also known as an expression automaton or a generalized nondeterministic finite state machine, is a variation of a nondeterministic finite automaton (NFA) where each transition is labeled with any regular expression.

New!!: Finite-state machine and Generalized nondeterministic finite automaton · See more »

Hamburg University of Applied Sciences

The Hamburg University of Applied Sciences is an institution of higher education and applied research located in Hamburg, Germany.

New!!: Finite-state machine and Hamburg University of Applied Sciences · See more »

Hidden Markov model

Hidden Markov Model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved (i.e. hidden) states.

New!!: Finite-state machine and Hidden Markov model · See more »

Implication table

An implication table is a tool used to facilitate the minimization of states in a state machine.

New!!: Finite-state machine and Implication table · See more »

Input (computer science)

In computer science, the general meaning of input is to provide or give something to the computer, in other words, when a computer or device is receiving a command or signal from outer sources, the event is referred as input to the device.

New!!: Finite-state machine and Input (computer science) · See more »

International Telecommunication Union

The International Telecommunication Union (ITU; Union Internationale des Télécommunications (UIT)), originally the International Telegraph Union (Union Télégraphique Internationale), is a specialized agency of the United Nations (UN) that is responsible for issues that concern information and communication technologies.

New!!: Finite-state machine and International Telecommunication Union · See more »

Introduction to Automata Theory, Languages, and Computation

Introduction to Automata Theory, Languages, and Computation is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation.

New!!: Finite-state machine and Introduction to Automata Theory, Languages, and Computation · See more »

Lexical analysis

In computer science, lexical analysis, lexing or tokenization is the process of converting a sequence of characters (such as in a computer program or web page) into a sequence of tokens (strings with an assigned and thus identified meaning).

New!!: Finite-state machine and Lexical analysis · See more »


Linguistics is the scientific study of language, and involves an analysis of language form, language meaning, and language in context.

New!!: Finite-state machine and Linguistics · See more »


Logic (from the logikḗ), originally meaning "the word" or "what is spoken", but coming to mean "thought" or "reason", is a subject concerned with the most general laws of truth, and is now generally held to consist of the systematic study of the form of valid inference.

New!!: Finite-state machine and Logic · See more »

Logic gate

In electronics, a logic gate is an idealized or physical device implementing a Boolean function; that is, it performs a logical operation on one or more binary inputs and produces a single binary output.

New!!: Finite-state machine and Logic gate · See more »

Markov chain

A Markov chain is "a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event".

New!!: Finite-state machine and Markov chain · See more »


Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.

New!!: Finite-state machine and Mathematics · See more »

Mealy machine

In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs.

New!!: Finite-state machine and Mealy machine · See more »

Model of computation

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how a set of outputs are computed given a set of inputs.

New!!: Finite-state machine and Model of computation · See more »

Moore machine

In the theory of computation, a Moore machine is a finite-state machine whose output values are determined only by its current state.

New!!: Finite-state machine and Moore machine · See more »

Moore reduction procedure

In computer science, the Moore reduction procedure is a method used for DFA minimization.

New!!: Finite-state machine and Moore reduction procedure · See more »

National Institute of Standards and Technology

The National Institute of Standards and Technology (NIST) is one of the oldest physical science laboratories in the United States.

New!!: Finite-state machine and National Institute of Standards and Technology · See more »

Nondeterministic finite automaton

In automata theory, a finite state machine is called a deterministic finite automaton (DFA), if.

New!!: Finite-state machine and Nondeterministic finite automaton · See more »

Partial function

In mathematics, a partial function from X to Y (written as or) is a function, for some subset X ′ of X.

New!!: Finite-state machine and Partial function · See more »

Petri net

A Petri net, also known as a place/transition (PT) net, is one of several mathematical modeling languages for the description of distributed systems.

New!!: Finite-state machine and Petri net · See more »


Philosophy (from Greek φιλοσοφία, philosophia, literally "love of wisdom") is the study of general and fundamental problems concerning matters such as existence, knowledge, values, reason, mind, and language.

New!!: Finite-state machine and Philosophy · See more »

Powerset construction

In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language.

New!!: Finite-state machine and Powerset construction · See more »

Processor register

In computer architecture, a processor register is a quickly accessible location available to a computer's central processing unit (CPU).

New!!: Finite-state machine and Processor register · See more »

Programmable logic controller

A programmable logic controller (PLC), or programmable controller is an industrial digital computer which has been ruggedized and adapted for the control of manufacturing processes, such as assembly lines, or robotic devices, or any activity that requires high reliability control and ease of programming and process fault diagnosis.

New!!: Finite-state machine and Programmable logic controller · See more »

Programmable logic device

A programmable logic device (PLD) is an electronic component used to build reconfigurable digital circuits.

New!!: Finite-state machine and Programmable logic device · See more »

Pushdown automaton

In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.

New!!: Finite-state machine and Pushdown automaton · See more »

Quantum finite automata

In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process.

New!!: Finite-state machine and Quantum finite automata · See more »

Recursively enumerable language

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.

New!!: Finite-state machine and Recursively enumerable language · See more »

Regular language

In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be expressed using a regular expression, in the strict sense of the latter notion used in theoretical computer science (as opposed to many regular expressions engines provided by modern programming languages, which are augmented with features that allow recognition of languages that cannot be expressed by a classic regular expression).

New!!: Finite-state machine and Regular language · See more »


A relay is an electrically operated switch.

New!!: Finite-state machine and Relay · See more »

Richards controller

The Richards controller is a method of implementing a finite state machine using simple integrated circuits and combinational logic.

New!!: Finite-state machine and Richards controller · See more »


SCXML stands for State Chart XML: State Machine Notation for Control Abstraction.

New!!: Finite-state machine and SCXML · See more »


In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output.

New!!: Finite-state machine and Semiautomaton · See more »


In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse.

New!!: Finite-state machine and Semiring · See more »

Sequential logic

In digital circuit theory, sequential logic is a type of logic circuit whose output depends not only on the present value of its input signals but on the sequence of past inputs, the input history.

New!!: Finite-state machine and Sequential logic · See more »

Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

New!!: Finite-state machine and Shortest path problem · See more »

Software engineering

Software engineering is the application of engineering to the development of software in a systematic method.

New!!: Finite-state machine and Software engineering · See more »

Specification and Description Language

Specification and Description Language (SDL) is a specification language targeted at the unambiguous specification and description of the behaviour of reactive and distributed systems.

New!!: Finite-state machine and Specification and Description Language · See more »

State (computer science)

In information technology and computer science, a program is described as stateful if it is designed to remember preceding events or user interactions; the remembered information is called the state of the system.

New!!: Finite-state machine and State (computer science) · See more »

State diagram

A state diagram is a type of diagram used in computer science and related fields to describe the behavior of systems.

New!!: Finite-state machine and State diagram · See more »

State encoding for low power

State encoding assigns a unique pattern of ones and zeros to each defined state of a finite-state machine (FSM).

New!!: Finite-state machine and State encoding for low power · See more »

State pattern

The state pattern is a behavioral software design pattern that implements a state machine in an object-oriented way.

New!!: Finite-state machine and State pattern · See more »

State transition table

In automata theory and sequential logic, a state transition table is a table showing what state (or states in the case of a nondeterministic finite automaton) a finite semiautomaton or finite state machine will move to, based on the current state and other inputs.

New!!: Finite-state machine and State transition table · See more »

String (computer science)

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.

New!!: Finite-state machine and String (computer science) · See more »

Subshift of finite type

In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory.

New!!: Finite-state machine and Subshift of finite type · See more »

Theory of computation

In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.

New!!: Finite-state machine and Theory of computation · See more »

Token coin

In the study of numismatics, token coins or trade tokens are coin-like objects used instead of coins.

New!!: Finite-state machine and Token coin · See more »

Traffic light

Traffic lights, also known as traffic signals, traffic lamps, traffic semaphore, signal lights, stop lights, robots (in South Africa and most of Africa), and traffic control signals (in technical parlance), are signalling devices positioned at road intersections, pedestrian crossings, and other locations to control flows of traffic.

New!!: Finite-state machine and Traffic light · See more »

Transition system

In theoretical computer science, a transition system is a concept used in the study of computation.

New!!: Finite-state machine and Transition system · See more »

Tree automaton

A tree automaton is a type of state machine.

New!!: Finite-state machine and Tree automaton · See more »

Truth table

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arguments, that is, for each combination of values taken by their logical variables (Enderton, 2001).

New!!: Finite-state machine and Truth table · See more »


In mathematics, a tuple is a finite ordered list (sequence) of elements.

New!!: Finite-state machine and Tuple · See more »

Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

New!!: Finite-state machine and Turing machine · See more »


A turnstile, also called a baffle gate or turnstyle, is a form of gate which allows one person to pass at a time.

New!!: Finite-state machine and Turnstile · See more »

UML state machine

UML state machine, also known as UML statechart, is a significantly enhanced realization of the mathematical concept of a finite automaton in computer science applications as expressed in the Unified Modeling Language (UML) notation.

New!!: Finite-state machine and UML state machine · See more »

Unified Modeling Language

The Unified Modeling Language (UML) is a general-purpose, developmental, modeling language in the field of software engineering, that is intended to provide a standard way to visualize the design of a system.

New!!: Finite-state machine and Unified Modeling Language · See more »

Vending machine

A vending machine is an automated machine that provides items such as snacks, beverages, cigarettes and lottery tickets to consumers after money, a credit card, or specially designed card is inserted into the machine.

New!!: Finite-state machine and Vending machine · See more »

Vertex (graph theory)

In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).

New!!: Finite-state machine and Vertex (graph theory) · See more »

Virtual finite-state machine

A virtual finite state machine is a finite state machine (FSM) defined in a virtual environment.

New!!: Finite-state machine and Virtual finite-state machine · See more »

YAKINDU Statechart Tools

YAKINDU Statechart Tools (YAKINDU SCT) is a tool for the specification and development of reactive, event-driven systems with the help of finite-state machines.

New!!: Finite-state machine and YAKINDU Statechart Tools · See more »

Redirects here:

Accept state, Accepting state, Acceptor (finite-state machine), Deterministic automata, FSA Utilities, Finate state automata, Finite Automata, Finite State Automaton, Finite State Machine, Finite State Machines, Finite automata, Finite automaton, Finite state, Finite state acceptor, Finite state automata, Finite state automaton, Finite state grammar, Finite state language, Finite state machine, Finite state machines, Finite state recognizer, Finite state-machine, Finite-state automata, Finite-state automaton, Finite-state machines, Finite-state recognizer, Optimization of finite state machines, Recognizer, Recognizers, SFSM, Sequence detector, Sequence detectors, Start state, State Machine, State machine, State machines, State transition function, State-machine.


[1] https://en.wikipedia.org/wiki/Finite-state_machine

Hey! We are on Facebook now! »