Q1Theory of Computation

A Deterministic Finite Automaton (DFA) is a 5-tuple $(Q,\Sigma ,\delta ,q_0,F)$ where $Q$ is a finite set of states, $\Sigma$ is the input alphabet, $q_0\in Q$ is the start state, $F\subseteq Q$ is the set of final states, and $\delta :Q\times \Sigma \to Q$ is the transition function that maps each (state, symbol) pair to exactly one next state. A Non-deterministic Finite Automaton (NFA) is also a 5-tuple $(Q,\Sigma ,\delta ,q_0,F)$, but the transition function is $\delta :Q\times (\Sigma \cup \{ϵ\})\to 2^Q$, mapping a (state, symbol) pair to a set of possible next states, and permitting transitions on the empty string $ϵ$ without consuming input.

• Determinism: In a DFA, for every state and every input symbol there is exactly one defined transition. In an NFA, there can be zero, one, or many transitions for a given state-symbol pair.
• Epsilon transitions: NFAs may change state without consuming any input symbol (an $ϵ$-move); DFAs have no such facility.
• Completeness: A DFA transition function is total (every state has an outgoing edge for every alphabet symbol, possibly to a dead/trap state); an NFA's transition function may be partial.
• Acceptance: A DFA accepts a string if the single computation path ends in a final state. An NFA accepts a string if at least one of the possibly many computation paths ends in a final state.
• Memory during simulation: Simulating a DFA needs to track only the current state (O(1) extra memory). Simulating an NFA directly requires tracking a set of current states.
• Size: An NFA for a given language can be exponentially smaller than the minimal equivalent DFA, since subset construction can blow up the number of states to as many as $2^n$ for an $n$-state NFA.
• Ease of construction: NFAs are usually far easier to construct directly from a regular expression (e.g., via Thompson's construction) because non-determinism and $ϵ$-moves let each RE operator be translated locally without needing to resolve choices immediately.

Despite these operational differences, DFAs and NFAs are equivalent in the languages they can recognize: both characterize exactly the class of regular languages. This is proved constructively using the subset construction (also called the powerset construction), which converts any NFA with $n$ states into an equivalent DFA whose states are subsets of the NFA's state set. Each DFA state $q_D\subseteq Q_N$ represents 'the set of NFA states the machine could simultaneously be in after reading a given prefix,' and the DFA start state is the $ϵ$-closure of the NFA's start state. Formally, ${\delta }_D(S,a)={\bigcup }_{q\in S}ϵ\text{-closure}({\delta }_N(q,a))$ for $S\subseteq Q_N$, and a subset $S$ is a final DFA state iff it contains at least one NFA final state. Because the resulting DFA simulates all NFA branches in parallel by tracking the set of reachable states, it accepts precisely the same language as the NFA. Conversely, every DFA is trivially an NFA (one whose transition function happens to return singleton sets and that never uses $ϵ$-moves), so the class of NFA-recognizable languages is a superset of DFA-recognizable languages, and the subset construction shows the reverse containment, giving equality. In practice, NFAs are preferred for compact specification and quick construction from patterns, while DFAs are preferred for efficient string matching at runtime since table lookup requires no backtracking or branching, which is why lexical analyzers in compilers typically convert an NFA description of tokens into a DFA (often minimized) before scanning source code.