Deterministic finite automaton

A deterministic finite automaton is a finite-state machine whose transition function assigns exactly one next state to every state and input symbol. It accepts a string when processing that string ends in an accepting state.

Transition function: A function that maps a state and input symbol to a next state. It formalizes the automaton’s requirement to choose exactly one next state.
Formal language: A set of finite strings over an alphabet. A deterministic finite automaton recognizes a formal language by accepting exactly its strings.
Nondeterministic finite automaton: A finite automaton that may have multiple possible next states for a state and input symbol. It allows branching where a deterministic finite automaton must choose one next state.
Lexical analysis: The compiler stage that groups source-code characters into tokens. Lexers commonly use deterministic finite automata to recognize token patterns.
Initial state: The designated state where a computation begins. Every input string is processed starting from this state.
Alphabet (formal languages): A finite set of symbols used to form strings. The automaton’s transition function has one choice for every alphabet symbol.
Deterministic pushdown automaton: A pushdown automaton whose permitted move is uniquely determined by its state and input or stack symbol. Its stack provides memory that a deterministic finite automaton does not have.
Regular expression engine: Software that searches or matches text according to regular-expression patterns. Many engines compile regular patterns into finite automata for matching.
Accepting state: A state designated as successful when a computation ends there. The ending state determines whether the processed string is accepted.
String (computer science): A finite sequence of symbols drawn from an alphabet. Strings are the inputs the automaton processes.

Linked from 11 pages