[10] (Converting NFA to DFA) A DFA A has a finite number of states, including a distinguished start state and some distinguished accepting states. At every step, A reads the next input symbol and changes its state according to the current state and the input symbol. If A has more than one alternative at some step, then A is nondeterministic

(NFA). If A is in an accepting state when it reads a distinguished end marker, then A accepts the input. Otherwise A rejects it. It is well known that every NFA can be converted to a DFA. Use an incompressibility argument to prove that there exists an NFA with n states such that the smallest DFA accepting the same language has Ω(2n) states.

Comments. Hint: use Lk = {x : the kth bit of x from the right is 1}.

This problem can also be solved by a simple counting argument.