##  [Finite Automaton](/finite-automaton-0) 

 Definition

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

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

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

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

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

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

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

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

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.