Consider the language $L= \{ x\in \{0,1\}^* |x$ ends with $00 \}$

The Nerode relation $R_L$ says

$xR_Ly \iff \forall z\in \Sigma^*:xz\in L\iff yz\in L$

By looking at the language : I can conclude that the equivalence classes should be something like

$[\epsilon]=\{x|x$ doesnt end with $0\}$

$[0]=\{x|x$ ends with $0$ but not with $00\}$

$[00]=\{x|x$ ends with $00\}$

My question is : Is there any smart way to find the equivalence classes of any Language ? Can we do this algorithmically?

  • 1
    $\begingroup$ Does DFA minimization answer your needs? $\endgroup$ – Yuval Filmus May 5 '18 at 21:09
  • 1
    $\begingroup$ Before this question can be answered, you need to formulate it formally: explain what is the input, and what is the desired output. $\endgroup$ – Yuval Filmus May 5 '18 at 21:12
  • 1
    $\begingroup$ This information should be merged into the post. You also need to explain how the language and equivalence classes are encoded. Be as formal as possible. Imagine writing an actual program- what would be its input and output? $\endgroup$ – Yuval Filmus May 5 '18 at 21:17
  • 1
    $\begingroup$ Your problem isn't well-defined. It's hard to answer vague questions. If your language is given as a DFA, then as pointed out above, in a sense you can find the equivalence classes by minimizing the DFA. $\endgroup$ – Yuval Filmus May 5 '18 at 21:24
  • 1
    $\begingroup$ What kind of grammar? If I remember correctly, given a context-free grammar, it is undecidable whether it generates a regular language. $\endgroup$ – Yuval Filmus May 5 '18 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.