dfa

DFA stands for Deterministic Finite Automaton. It is a theoretical model used in formal language theory to recognize regular languages. A DFA consists of a finite set of states Q, an input alphabet Σ, a transition function δ, a start state q0 ∈ Q, and a set of accept states F ⊆ Q. The transition function maps Q × Σ to Q, and in a deterministic automaton, for every state and input symbol there is exactly one next state. Some presentations allow partial DFAs where a transition may be undefined; such automata can be completed by adding a dead state.

Processing an input string over Σ begins at q0 and follows δ for each symbol in order. If, after the last symbol, the current state is in F, the string is accepted; otherwise it is rejected. The set of strings accepted by a DFA over Σ is called a regular language. DFAs are closed under union, concatenation, and Kleene star, and every DFA corresponds to a regular expression.

DFAs are related to nondeterministic finite automata (NFAs); for every NFA there exists an equivalent DFA, obtained via the subset construction. Conversely, DFAs are typically memory-efficient and fast to run, since each input symbol causes a single state transition.

Minimization: many DFAs can be reduced to an equivalent machine with the fewest possible states using algorithms such as Hopcroft’s or Moore’s. These minimize existing DFAs but do not change their recognized language.

Applications include lexical analysis in compilers, text search, pattern matching, and formal verification of systems and protocols.