If L is a language accepted by a DFA with n states, then the complement of L, $L_{bar}$, is accepted by a DFA with how many states?
Complementing a DFA is done by swapping accept and non-accept states without changing the state set. Thus, state count remains n.
Which of the following operations on regular languages ALWAYS produce a regular language?
Regular languages are closed under all boolean operations (Union, Intersection, Complement, Set Difference) and Kleene Star.
What is the minimum number of states in a DFA accepting strings over {a, b} where every 'a' is immediately followed by 'b'?
Use three states: q0 (start/accept), q1 (just read an 'a' and must read 'b' next), and q2 (dead state after an 'a' is not followed by 'b'). Thus the minimum is 3 states.
How many states are in the minimal DFA accepting strings over {a, b} whose binary value when interpreted as a binary number (with $a=1, b=0$) is divisible by 3?
The DFA tracks the remainder modulo 3 of the binary value, giving three states for remainders 0, 1, and 2.
If a language L is accepted by an NFA with k states, what is the maximum number of states in a minimal DFA for L?
The subset construction uses subsets of the NFA states, giving up to $2^k$ possible states in the DFA.