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?
