1
$\begingroup$

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)?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I guess I'm not just mathematically mature enough but I don't really understand the purpose of Lemma 1. So if I wanted to prove the statement on my own, could I have chosen different strings for $w_0,w_1,$ etc. and find strings to append to each combination pair so that one is accepted and one is rejected to show a contradiction? Unfortunately, I'm not familiar with the Myhill-Nerod theory, so I'm not exactly sure whether your answer implicity answered the second question.. $\endgroup$ – Christopher Dec 2 '18 at 0:50
  • $\begingroup$ Lemma 1 is an abstraction of the argument in your Proposition 5. This kind of argument only proves a lower bound on the number of states. Imagine applying the same argument to a strict subset of the words, and you can answer the second question on your own. Following that, the rest of my answer should make sense. $\endgroup$ – Yuval Filmus Dec 2 '18 at 0:53
  • $\begingroup$ I appreciate the help and trying to walk me through it but I just can't seem to wrap my head around it. Having done this proof, doesn't it only show that the number of states cannot be less than six? How do I know that I can't just find a set of, say seven strings and show that the minimum is now seven instead of six? Is that implicitly shown in the Proposition 5? $\endgroup$ – Christopher Dec 2 '18 at 2:08
  • $\begingroup$ Right, it only shows that the number of states has to be at least six. Unfortunately I haven't read Proposition 5 or its proof, but one way to show that you can't find a set of seven strings is by describing a DFA containing six states. $\endgroup$ – Yuval Filmus Dec 2 '18 at 2:15
  • $\begingroup$ @Christopher, figure 3 in that articles shows a DFA with 6 states. $\endgroup$ – Apass.Jack Dec 2 '18 at 6: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.