Finite-state machine

A finite-state machine is an abstract model with finitely many states and transitions that specify how inputs change its current state.

State transition: A change from one state of a system to another under a specified condition or input. A transition is the step that moves the machine between states.
Automaton: An abstract machine that processes inputs according to a formal set of states and rules. Finite-state machines are one finite-memory kind of automaton.
Nondeterministic finite automaton: A finite automaton that may have multiple possible next states for one state and input. It differs in transition choices, though it recognizes the same languages as deterministic machines.
Finite-state transducer: A finite-state machine that produces output strings while processing input strings. It extends state-based processing to transformations such as text and speech conversion.
Transition table: A tabular representation of the next state or output for each current state and input. It lays out the machine’s transition rules in a compact form.
Alphabet (formal languages): A finite set of symbols from which strings in a formal language are formed. The machine’s input symbols are drawn from an alphabet.
Pushdown automaton: An automaton equipped with a stack, giving it memory beyond a finite set of states. Its stack lets it recognize some languages that finite-state machines cannot.
Lexical analysis: The compiler stage that groups source-code characters into tokens. Lexers commonly implement token-recognition rules with finite automata.
Initial state: The designated state in which a system or computation begins. It determines where processing starts before any input arrives.
String (computer science): A finite sequence of symbols drawn from an alphabet. A machine commonly processes an input as a string of symbols.

Linked from 38 pages