1
$\begingroup$

I have the following task (no homework).

Find all equivalence classes of the Myhill-Nerode relation of the language $$ \mathrm{A} \triangleq\{w \in \Sigma^{*} | w\text{ does not end with }01\}\,. $$

Because I have no Idea how I to find does classes -I know the theory, but I can't use it -. So I build a DFA (what i should not do):

enter image description here

Now I know there has to be 3 different classes (because the DFA is minimized), but again, I have no idea how to find them. I hope you can help me a little bit, because I write a test paper in 5 weeks and this will be a big Troublemaker.

Improve this question
$\endgroup$
5
  • $\begingroup$ Each state in the minimized DFA corresponds to a class. Any input word which causes the DFA to reach a state is a member (and, thus, a representative) of the corresponding class. $\endgroup$
    – dkaeae
    Commented Jan 31, 2019 at 14:02
  • $\begingroup$ Hint: You know that in a minimized DFA, the runs of two equivalent words will end up in the same state. Now given a minimized DFA $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$, what is the language of all words tha have runs that end in e.g. $q_1$ (or of the automaton $(Q, \Sigma, \delta, q_0, \{q_1\})$? $\endgroup$
    – ttnick
    Commented Jan 31, 2019 at 14:02
  • $\begingroup$ When you think you know the theory but you don't know how to apply it to a problem that is literally about that theory, that usually means that you don't really know the theory. $\endgroup$
    – David Richerby
    Commented Jan 31, 2019 at 15:23
  • $\begingroup$ @DavidRicherby yes maybe your right. $\endgroup$
    – Kevin.M
    Commented Jan 31, 2019 at 16:01
  • $\begingroup$ @ttnick 11 , (10 and 00) and 01 so this are my classes? $\endgroup$
    – Kevin.M
    Commented Jan 31, 2019 at 16:01

1 Answer 1

Reset to default
1
$\begingroup$

Two strings $x$ and $y$ are in the same Myhill–Nerode class if they can't be distinguished by adding the same string onto the end of them. That is, they're in the same class if, for all strings $z$, either $xz$ and $yz$ are both in the language or neither of them is.

So, for example, the strings $00$ and $01$ are in different classes because we can distinguish then by adding $1$: $001$ is in the language and $011$ is not. In fact, they're already distinguished by the empty string $\epsilon$, since $01$ is in the language but $00$ is not.

In your case, you can shortcut this because the notion of indistinguishability corresponds exactly to minimal automata: the classes are exactly the sets of strings that take you to each state of the automaton.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So what you try to say is. That I have to put all words (prefixes) with the same suffix, with they need to fulfill the language condition, in one class. Aso there has to be a class with never fulfill the condition? For example $[01 ]=\{w \in \Sigma^{*} | w\text{ ends with }01\}\,.$ would be the class with no word will never be in A? $\endgroup$
    – Kevin.M
    Commented Jan 31, 2019 at 15:48
  • $\begingroup$ No. A class may contain words that are in $A$ and words that are not in $A$. The criterion is as I stated in the first paragraph. In the case of the language $A$, every string has extensions that are in $A$, because membership of $A$ depends only on the end of the word. For example, for any string $x$, the string $x01$ is in $A$. $\endgroup$
    – David Richerby
    Commented Jan 31, 2019 at 22:29

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.