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 &gt; 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 &gt; 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 &lt; i &lt; k$, so we are done. Is this a correct attempt?
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$.