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?

  • $\begingroup$ 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$. $\endgroup$ May 18 at 14:23
  • $\begingroup$ Right so, it may have a cycle of length $2$. My argument still holds though, since I can pump down even further, correct? $\endgroup$
    – Tom Finet
    May 18 at 14:31
  • $\begingroup$ 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. $\endgroup$
    – Tom Finet
    May 18 at 14:59
  • 1
    $\begingroup$ Would the language $\{ 0^k \}$ be a candidate? $\endgroup$ May 18 at 19:40
  • 1
    $\begingroup$ Right, the argument works, and it is basically the proof of the pumping lemma. $\endgroup$ May 20 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$.

  • $\begingroup$ I added my second attempt to my question, would greatly appreciate knowing if it is correct. @Yuval Filmus $\endgroup$
    – Tom Finet
    May 18 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.