Transition function

A transition function maps a machine’s current state and input symbol to its next action and state. Its outputs specify how the machine changes as it processes an input.

Deterministic finite automaton: A finite-state machine whose transition function assigns exactly one next state to each state and input symbol. Its transition function makes every input determine a unique next state.
Finite-state machine: A computational model with finitely many states that changes state in response to input. A transition function is the rule governing its state changes.
Regular language: A language that can be recognized by a finite automaton. A finite automaton’s transition function determines which strings it accepts.
Transition relation: A relation specifying which next configurations are possible from each current configuration. Unlike a function, it can permit multiple next configurations for the same input.
Nondeterministic finite automaton: A finite-state machine that may have multiple possible next states for a state and input symbol. Unlike a deterministic transition function, its transition relation can offer several next states.
State (computer science): A configuration that records the relevant condition of a system at a particular point in computation. The current state is one of the transition function’s inputs.
Lexical analysis: The process of grouping source-code characters into tokens for a compiler or interpreter. Lexer generators encode token-recognition rules as finite-state transitions.
Probabilistic transition function: A rule assigning probability distributions over next states to current states and inputs. Its output is a distribution rather than one definite next action and state.
Mealy machine: A finite-state machine whose outputs are determined by its current state and input symbol. Its transition function can specify both the next state and the output produced on a step.
Input alphabet: A finite set of symbols that a formal machine can receive as input. Each input symbol selects which transition rule applies in a given state.

Linked from 11 pages