1
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Commented Jan 22, 2022 at 14:57
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Commented Jan 22, 2022 at 14:59
  • $\begingroup$ 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^*$? $\endgroup$ Commented Jan 22, 2022 at 15:02
  • $\begingroup$ Yup, that's more or less it! $\delta^*(q_s, u)$ is always defined, so $u\in reach(\delta^*(q_s, u))$. $\endgroup$
    – Nathaniel
    Commented Jan 22, 2022 at 15:03
  • $\begingroup$ Okay, thank you for the clarification and the help! $\endgroup$ Commented Jan 22, 2022 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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