Given a language $A = \{a^nb^n : n >= 0\}$, how would one go about characterizing the equivalence classes of this language, in order to apply Myhill-Nerode to show it is not regular? The idea and meaning of "characterizing equivalence classes" is what I am struggling with.

  • $\begingroup$ I suggest that you go back to the definition of equivalence class, in this particular context, and refine your question to address what exactly is your difficulty. $\endgroup$ – André Souza Lemos Oct 18 '16 at 20:23
  • $\begingroup$ @AndréSouzaLemos I guess that is my difficulty: I don't know what an equivalence class is in this context. I understand the idea of an equivalence relation between states of a DFA - is that what we build the equivalence classes out of? An equivalence class for a state $x$ is the set of all states $y$ for which the equivalence relation ~ holds? $\endgroup$ – socrates Oct 18 '16 at 20:32
  • $\begingroup$ The notion of equivalence class here comes from understanding what is a distinguishing extension. In other words, the definition of the relation that creates these classes of equivalence comes from the definition of the language itself. $\endgroup$ – André Souza Lemos Oct 18 '16 at 20:36
  • $\begingroup$ en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem $\endgroup$ – André Souza Lemos Oct 18 '16 at 20:37
  • $\begingroup$ You don't need to find all equivalence classes in order to show that the language is not regular. It suffices to exhibit an infinite set of words which are pairwise inequivalent. $\endgroup$ – Yuval Filmus Oct 18 '16 at 20:52

The notion of equivalence is that of indistinguishability. Given a language $L \subseteq \Sigma^{\ast}$, we say that strings $x$ and $y$ are indistinguishable wrt. $L$, written $x \, I_L \, y$, if we have that for every $z \in \Sigma^{\ast}$ that $xz \in L \iff yz \in L$.

The Myhill-Nerode theorem tells us that a language $L$ is a regular language iff the set of equivalence classes of $I_L$ is finite.

To show that $L = \{ w \in \{ a,b\}^{\ast} \mid \exists n \geq 0. w = a^n b^n \}$ is not regular, we simply have to show that the set of equivalence classes of $I_L$ is infinite.

So consider a string $w \in \{ a,b\}^{\ast}$. The set of all strings $w$ not of the form $a^i b^j$ where $i \geq j$ forms an equivalence class, since for no $z$ we have that $w_1 z \in L$ if $w$ is not of the form $a^i b^j$.

Moreover, every string of the form $a^i b^j$ where $i \geq j$ can only be indistinguishable from itself. So every such string forms an equivalence class containing only this single string.

Consequently, $I_L$ has infinitely many equivalence classes.

  • $\begingroup$ As a follow up, does $[x]$, where $[x]$ is the $∼$-equivalence class of $x$, mean the set of all strings that are equivalent to $x$ under the equivalence relation ~? $\endgroup$ – socrates Oct 18 '16 at 22:44
  • $\begingroup$ Also, is there a reason you specified $i≥j$; couldn't we simply have $i \neq j$? $\endgroup$ – socrates Oct 18 '16 at 22:52
  • $\begingroup$ $[x]$ is indeed the equivalence class containing $x$. And note that for strings of the form $a^ib^j$ there will only exist an $z$ such that $a^ib^jz \in L$ if there are at least as many $a$s as there are $b$s. $\endgroup$ – Hans Hüttel Oct 19 '16 at 3:34

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.