In the formal definition of a DFA, the transition function δ maps to which of the following?
AA set of possible next states, one per input symbol
BExactly one next state for each (state, input symbol) pair
CA set of accept states reachable from a given state
DA string of output symbols produced by processing the input
δ: Q × Σ → Q maps each (state, symbol) pair to exactly one next state — this determinism is what distinguishes a DFA from an NFA. There is never ambiguity about where to go next.
Question 2 True / False
A complete DFA can get 'stuck' on an input string — that is, reach a configuration where no transition is defined for the next symbol, and the machine halts without accepting or rejecting.
TTrue
FFalse
Answer: False
A complete DFA has a transition defined for every (state, symbol) pair — no exceptions. Languages that would naively leave some transitions undefined are handled by adding a dead (trap) state that all 'undefined' transitions lead to. Once in the dead state, the machine stays there and rejects. The machine always processes the entire input.
Question 3 Short Answer
What fundamental limitation prevents DFAs from recognizing the language {aⁿbⁿ | n ≥ 1} (equal numbers of a's followed by equal numbers of b's)?
Think about your answer, then reveal below.
Model answer: A DFA has no memory beyond its current state. Recognizing aⁿbⁿ requires counting how many a's were seen so it can verify an equal number of b's — but a finite number of states cannot represent an unbounded count. A pushdown automaton (with a stack) is needed.
This is the canonical example of a non-regular language. The pumping lemma for regular languages formally proves that no DFA can recognize it. The key insight is that DFA 'memory' is bounded by |Q|; any property requiring unbounded counting falls outside the class of regular languages.