# Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less

I am trying to prove that for every $$k > 1$$, there exists a language $$A_k \subseteq \{0, 1\}^*$$ such that a DFA accepting $$A_k$$ has $$k$$ states but no less.

I thought about proving this in two ways: constructively, or by contradiction.

By Contradiction: For some $$k > 1$$, suppose there is no language $$A_k \subseteq \{0, 1\}^*$$ where a DFA accepting $$A_k$$ exists with exactly $$k$$ states but no less. Then any language $$L \subseteq \{0, 1\}^*$$, that has an accepting DFA with $$n$$ states, also has an accepting DFA with $$n - 1$$ states. Extending this reasoning downward, this implies that every $$L$$ has an accepting DFA with $$1$$ state. This is a contradiction.

By construction: Let $$A_k = \{w \in \{0, 1\}^* | w \text{ has } 0^{k - 1} \text{ as a substring}\}$$. But now I need to prove that $$A_k$$ cannot be accepted by a DFA with less than $$k$$ states. I am unsure of how to do this even though it feels true intuitively.

Is my proof by contradiction valid and is the proof by construction doable? Maybe both are wrong and I need to use some other perspective.

Attempt 2:

We can easily construct a DFA with $$k$$ states, call it $$M_k$$, that accepts the language $$A_k = \{w \in \{0, 1\}^* | w \text{ has } 0^{k - 1} \text{ as a substring}\}$$

Suppose for contradiction that there exists a DFA, $$M_{k - 1}$$, accepting $$A_k$$ with $$k - 1$$ states. Consider the string $$w = 0^{k - 1} \in A_k$$, we can apply the pumping lemma because $$|w| \geq k - 1$$. Thus, the run of $$w$$ on $$M_{k - 1}$$ must contain a cycle of length 1 (since $$|w| = k - 1$$).

Then $$M_{k - 1}$$ actually accepts strings of the form $$w' = 0^x \cdot 0^i \cdot 0^z$$ where $$i \geq 0$$, $$x + 1 \leq k - 1$$ and $$x + z + 1 = k - 1$$. Letting $$i = 0$$, we see $$M_{k - 1}$$ accepts $$0^{k - 2} \not \in A_k$$. A contradiction.

This reasoning is applicable to every $$M_i$$ with $$1 < i < k$$, so we are done. Is this a correct attempt?

• The conclusion that the run of $w$ on $M_{k-1}$ must contain a cycle of length 1 is wrong. Consider $k = 3$ and a run involving states $q_0,q_1,q_0$. May 18, 2021 at 14:23
• Right so, it may have a cycle of length $2$. My argument still holds though, since I can pump down even further, correct? May 18, 2021 at 14:31
• If a cycle longer than 1 exists for $0^{k - 1}$, then surely it would not be in $A_k$. In your example, it starts from $q_0$ and ends in $q_0$, which means it would accept $\epsilon \not in A_k$ if your run is accepting. May 18, 2021 at 14:59
• Would the language $\{ 0^k \}$ be a candidate? May 18, 2021 at 19:40
• Right, the argument works, and it is basically the proof of the pumping lemma. May 20, 2021 at 14:03

Your first approach doesn't quite work. If it is not the case that for any $$k$$ there is some language that requires exactly $$k$$ states, then all you know is that there exists a single $$n$$ such that every $$n$$-state DFA can be reduced to an equivalent DFA with fewer states.
The second approach does work, and requires a lower bound technique such as the pumping lemma (the pumping constant is the number of states) or Myhill–Nerode theory. Try the following language: all words whose length is a multiple of $$k$$.