What is the minimum number of states in a DFA accepting all binary strings containing '101' as a substring?
States correspond to prefixes of '101': $\epsilon (start), '1', '10'$, and '101' (trap/accept state). Minimum states = 4.
What is the minimum number of states in a DFA that accepts all binary strings starting with '10' and ending with '01'?
The DFA must enforce the prefix 10, then track the last two symbols needed to ensure the string ends in 01, plus a dead state for strings that fail the required prefix. The minimal complete DFA has 6 states.
Consider an NFA with n states. What is the maximum number of states in an equivalent minimized DFA?
Subset construction can yield up to $2^n$ states in the worst case (e.g., matching the n-th character from the end).
A minimal DFA accepting all strings over {a, b} where the length of the string is divisible by 5 has how many states?
Track the length modulo 5: residues 0, 1, 2, 3, 4. Thus 5 states are necessary and sufficient.
Which of the following formal components is NOT part of a standard 5-tuple finite automaton $M = (Q, \Sigma, \delta, q0, F)$?
Stack alphabet $\Gamma$ is part of a Pushdown Automaton (PDA), not a finite automaton.