# DFA and a Partition of $\Sigma^*$

So I'm learning about Myhill-Nerode relations and as an introduction, the book describes possible partitions for $$\Sigma^*$$. As an example, given a language $$L$$, a partition of $$\Sigma^*$$ would be $$\{L, \overline{L}\}$$.

Suppose there is a DFA for $$L$$, the book continues by creating the following notion: For a $$q \in Q$$ (where $$Q$$ are the states in the DFA), the set $$reach(q)$$ is a subset of $$\Sigma^*$$:

$$reach(q) = \{w \in \Sigma^*$$ $$|$$ $$\delta^*(q_s, w) = q\}$$

i.e. The set of strings that bring you from the starting state $$q_s$$ to $$q$$.

Then it is said that $$\{reach(q)$$ $$|$$ $$q \in Q\}$$ is a partition of $$\Sigma^*$$ if every state $$q$$ is reachable from $$q_s$$ and for every $$q \in Q$$ and every symbol $$a \in \Sigma$$, the transition $$\delta(q, a)$$ is defined.

I don't see how this creates a partition of $$\Sigma^*$$ and certainly not how to prove this. Any help is appreciated.

Reminder: a family $$S_1, …, S_n$$ is a partition of $$S$$ if and only if it verifies three properties:

• for each $$i$$, $$S_i \neq \emptyset$$;
• for $$i \neq j$$, $$S_i\cap S_j = \emptyset$$;
• $$\bigcup\limits_{i=1}^nS_i = S$$.

I will give you hints for each of those points:

• the first point is proved using the fact that each state $$q\in Q$$ is reachable from $$q_s$$;
• the second point is proved using the fact that the automaton is deterministic;
• the third point is proved using the fact that $$\delta(q, a)$$ is always defined for all $$q\in Q$$ and $$a\in \Sigma$$.

Hope that helps!

• I understand the first two hints, those make complete sense to me. I don't however see how to use the third hint to say that the union of all $reach(q)$ would result in $\Sigma^*$. Could you perhaps clarify? Commented Jan 22, 2022 at 14:57
• Given any word $u\in \Sigma^*$, reading it in the automaton will always get you in some state $q\in Q$, because the DFA is complete. Commented Jan 22, 2022 at 14:59
• So what it would mean is that for any word $u \in \Sigma^*$, there is one state $q \in Q$ that is reached (otherwise the second property of a partition for a set would not be satisfied, I think?) and because this holds true for every word $u$ (since the automaton is complete), it hold for $\Sigma^*$? Commented Jan 22, 2022 at 15:02
• Yup, that's more or less it! $\delta^*(q_s, u)$ is always defined, so $u\in reach(\delta^*(q_s, u))$. Commented Jan 22, 2022 at 15:03
• Okay, thank you for the clarification and the help! Commented Jan 22, 2022 at 15:04