Question

Consider the languages ${\mathbf{C}}_{\mathrm{k}}$defined in Problem 1.60. Prove that for each${\mathbf{k}}_{}$ , no DFA can recognize${\mathbf{C}}_{\mathrm{k}}$ with fewer than${\mathbf{2}}^{\mathbf{K}}$ states.

Short answer

No DFA can recognize${\mathrm{C}}_{\mathrm{k}}$ with fewer than $2^{\mathrm{k}}$states is proved by Myhill-Nerode.

Step-by-step solution

Deterministic finite automata.

Deterministic finite automata (or DFA) are finite state machines that accept or reject strings of characters by parsing them through a sequence that is uniquely determined by each string. The term “deterministic” refers to the fact that each string, and thus each state sequence, is unique.

Myhill-Nerode for recognize Ck with fewer than 2k states.

There are clearly $2^{\mathrm{k}}$possible length-$\mathrm{k}$ input strings over $\{0,1\}$Assume for the sake of argument that there is a DFA Deterministic finite automata, $\mathrm{k}$that accepts the $\mathrm{k}$ from the end is $1$ language and that $\mathrm{k}$ has $\mathrm{m}<2^{\mathrm{n}}$. We don't have enough states to assign a unique one to every possible length- $\mathrm{k}$input, so there must be some state where we wind up after reading two different strings ${\mathrm{b}}_1{\mathrm{b}}_2\mathrm{.........}{\mathrm{b}}_{\mathrm{n}}$.

Since ${\mathrm{a}}_1{\mathrm{a}}_2\mathrm{........}{\mathrm{a}}_{\mathrm{n}}\ne {\mathrm{b}}_1{\mathrm{b}}_2\mathrm{...........}{\mathrm{b}}_{\mathrm{n}}$ they must differ in at least one place. Suppose without loss of generality that ${\mathrm{b}}_{\mathrm{i}}=0$.

If $\mathrm{i}=2$ , we're in state after reading a strings and also after reading its b strings. Suppose that from state on input zeroand then pass to state p, then in state p after reading a strings and also after reading b strings. In the former case, a strings has its to the last state, character from the end equal to one so p must be an accept state, but b strings does not so pp must not be an accepting state, again a contradiction.

Continuing, to see that no matter where the two inputs differ, by appending $\mathrm{i}=2$zeros (or anything else) to the two strings we'll find ourselves in a state which must be both accepting and non-accepting, so our original assertion, that $\mathrm{k}$has fewer than $2^{\mathrm{k}}$states, must have been false.

Hence, no DFA can recognize${\mathrm{C}}_{\mathrm{k}}$ with fewer than$2^{\mathrm{K}}$ states is proved by Myhill-Nerode