Trouble understanding this proof about the minimum number of states of a deterministic finite automaton

Question

So I was browsing online looking for the general structure to proving a DFA has a minimum of $n$ states for some $n$ and most of them use contradiction. However, I'm having a hard time understanding why the proof of proposition 5 works in proving the statement.

My understanding of the proof is that we assume there's a DFA consisting of $<n$ states and we construct $n$ strings. We then use the pigeonhole principle which would mean that two of these strings would have to be in the same state meaning that if we append a new string to both of these strings that are currently in the same state, these new strings should either both be accepted or rejected. This is where we want the contradiction.

I have two questions,

1) Do we have to make strings such that each would be in its own state or can we just make a set of any $n$ strings and so long as we can append something to each pair such that one of the strings in the pair is accepted and the other, rejected (leading to a contradiction)?

2) Does the proof imply that there is a DFA of exactly six states or just that there aren't any DFAs of five, four, three, two,or one state(s)?

Answer 1

Let $L$ be an arbitrary language. We say that two words $x,y$ are equivalent modulo $L$, written $x \stackrel{L}{\sim} y$, if for all words $z$, either both $xz,yz$ are in $L$, or both are not in $L$.

Lemma 1. Suppose that $x_1,\ldots,x_n$ are pairwise inequivalent modulo $L$. Then any DFA for $L$ must contain at least $n$ states.

Proof. Consider a DFA accepting $L$. Let $q_i$ be the state that the DFA reaches after reading $x_i$. I claim that $q_1,\ldots,q_n$ are all distinct. Indeed, consider any two states $q_i,q_j$. Since $x_i,x_j$ are inequivalent modulo $L$, there exists a word $z$ such that $x_iz \in L$ and $x_jz \notin L$, or vice versa; without loss of generality, assume the former. Since $x_iz \in L$, $\delta(q_i,z)$ must be an accepting state, whereas since $x_jz \notin L$, $\delta(q_j,z)$ must not be an accepting state. This shows that $q_i \neq q_j$. $\quad\square$

This is the method which is used in Proposition 5 that you mention.

What is the best lower bound that Lemma 1 can give us? Once you notice that $\stackrel L \sim$ is an equivalent relation, it is not hard to check that the maximum $n$ that you can choose is the number of equivalence classes of $\stackrel L \sim$:

Corollary 2. Any DFA for $L$ must contain at least $n$ states, where $n$ is the number of equivalence classes of $\stackrel L \sim$. In particular, if $\stackrel L \sim$ has infinitely many equivalence classes, then $L$ is not regular.

It is natural to ask whether this method is optimal:

1. If $L$ is not regular, can we always prove this using Corollary 2?
2. If $L$ is regular, is there always a DFA having $n$ states?

The positive answer to both questions is the main result of Myhill–Nerode theory, which you might learn about in the future.