DFAs

A deterministic finite automaton (DFA) is a mathematical model used to recognize regular languages. A DFA is a quintuple (Q, Σ, δ, q0, F): Q is a finite set of states, Σ is a finite input alphabet, δ: Q × Σ → Q is the transition function, q0 ∈ Q is the start state, and F ⊆ Q is the set of accepting states. At each step the machine is in exactly one state, and reading a symbol moves to the state δ(current, symbol).

The machine processes a string over Σ starting at q0. After consuming the entire input, the string is accepted if the current state belongs to F; otherwise it is rejected. DFAs are deterministic because for every state and input symbol there is exactly one next state; there are no epsilon moves or choices.

DFAs recognize regular languages. Every DFA accepts a regular language, and for every regular language there exists a DFA that recognizes it. NFAs, which may have multiple possible moves or epsilon transitions, have the same expressive power: every NFA has an equivalent DFA, obtainable by the subset construction.

DFAs can be minimized to a minimal DFA with the fewest states recognizing the same language. The minimal DFA is unique up to renaming of states. Minimization is typically performed by partition refinement algorithms.

In practice, DFAs are used in lexical analysis, pattern matching, and protocol verification. They run in time linear in the input length, since each input symbol causes a single transition. The number of states can grow with the complexity of the language, and sometimes becomes large.

DFAs are closed under union, concatenation, and Kleene star, underpinning the theory of regular languages and providing a foundation for efficient text processing and formal verification.