What is the minimum number of states needed for a DFA that recognizes binary strings where the number of 1s is divisible by 3?
A3 states — one for each remainder (0, 1, 2) when the count of 1s is divided by 3
B4 states — three for remainders plus a dedicated start state
CInfinitely many — the DFA must count arbitrary numbers of 1s, requiring unbounded memory
D2 states — one accepting state (divisible by 3) and one rejecting state (not divisible)
The DFA doesn't count 1s — it tracks remainder modulo 3, which takes only three values: 0, 1, and 2. One state per remainder suffices. The DFA starts in state 0 (remainder 0, which is also the accept state since 0 is divisible by 3), transitions on each 1 to the next remainder state, and stays put on 0s. This illustrates the key insight: the minimum states equal the distinct 'memories' about input history that matter — here, only the current remainder.
Question 2 Multiple Choice
Which of the following languages can a DFA recognize?
AAll binary strings containing an even number of 1s
BAll strings of the form aⁿbⁿ for n ≥ 1 (equal numbers of a's followed by equal numbers of b's)
CAll palindromes over the alphabet {a, b}
DAll strings where the total number of a's equals the total number of b's
Even number of 1s requires tracking only a parity bit — two states suffice (even-so-far, odd-so-far). The other three languages all require remembering an unbounded count: aⁿbⁿ needs to know exactly how many a's were seen before reading b's; palindromes require remembering the entire first half; equal counts require tracking the running difference. None of these can be captured by any finite state space, which is why they are not regular languages.
Question 3 True / False
In a DFA, the transition function need not be defined for most (state, symbol) pair — when no transition is defined for a given symbol, the DFA implicitly rejects the input.
TTrue
FFalse
Answer: False
By formal definition, the transition function δ: Q × Σ → Q must be TOTAL — defined for every state-symbol pair. To handle rejection, a 'dead state' (or 'sink state') is added: all undefined transitions lead to this state, which has self-loops on every symbol and is not an accept state. Keeping δ total is not just a technicality — it ensures the DFA's behavior is fully specified and composable with other formal operations (product construction, complementation, etc.).
Question 4 True / False
The minimum number of states in a DFA for a given language is related to the number of distinguishable histories of input prefixes — strings that will cause the DFA to behave differently going forward.
TTrue
FFalse
Answer: True
This is the Myhill-Nerode theorem: the minimum number of states in any DFA for a language L equals the number of equivalence classes of input strings under the relation 'x ≡ y if for all future strings z, xz ∈ L iff yz ∈ L.' Strings in the same class can be collapsed into a single state; strings in different classes must be distinguished. This gives both a lower bound on states and a canonical minimization algorithm.
Question 5 Short Answer
Why can a DFA recognize 'binary strings with an even number of 1s' but cannot recognize 'strings of the form aⁿbⁿ'? What property of DFAs explains the boundary?
Think about your answer, then reveal below.
Model answer: For even-1s, the only information needed about any prefix is parity — even or odd count of 1s so far. Two states capture all possible 'situations' a prefix can leave you in. For aⁿbⁿ, after reading n a's you must remember the exact value of n before comparing to the b's, and n can be arbitrarily large. No finite number of states can represent all possible values of n. DFAs recognize exactly the languages where what must be remembered about input history is expressible in finitely many distinct states — the regular languages. Any language requiring unbounded counting or unbounded memory exceeds DFA capacity.
The intuition is that a DFA's states are its entire memory — there is no stack, no tape, no counter. The finite state space is the fundamental constraint. This is why we need pushdown automata (with a stack) to recognize context-free languages like aⁿbⁿ, and Turing machines (with unbounded tape) for more complex languages. Each model in the Chomsky hierarchy adds one kind of memory.