A mathematical model of computation consisting of a finite set of states, an input alphabet, transition relations, a start state, and one or more accepting states; used to recognize regular languages. Variants include deterministic finite automata (DFA) and nondeterministic finite automata (NFA).

Principle

Computation advances by reading an input symbol and moving between states according to transition rules; acceptance is determined by whether the automaton reaches an accepting state after consuming the input. Nondeterminism allows multiple possible transitions; determinism has exactly one per symbol-state pair.

Demonstration

A lexer compiled from regular expressions is implemented as a DFA that scans source text left-to-right; state transitions encode the regular patterns for keywords, identifiers and literals so tokens are recognized in linear time with bounded memory.

Misapplication

Attempting to use a finite automaton to parse nested or context-free structures (like matched parentheses at arbitrary depth) which require unbounded memory (e.g., a stack); this leads to incorrect or incomplete recognition.

Consequence

Efficient, linear-time recognition of regular patterns with fixed, small memory overhead; allows compilation of regular expressions into compact transition tables and underlies many text-processing and hardware control applications.

Reversal

A pushdown automaton or Turing machine that augments state with unbounded memory (stack or tape) to recognize context-free or Turing-complete languages at the cost of more complex control and resource usage.

Boundary

Exactly characterizes regular languages; cannot recognize non-regular languages requiring unbounded memory. DFA and NFA are equivalent in expressive power though they differ in succinctness and implementation trade-offs.

Semantic Tension

Finite automaton versus regular expression: both define the same class of languages but differ between a state-machine operational view and a declarative pattern description; this distinction matters for construction and optimization.

Synthesis

A finite-state control that processes input symbols via state transitions, providing a compact, efficient mechanism to recognize exactly the regular languages; its limited memory (finite states) is both its constraint and its enabling property.