Progress so far:

firstly, I try and rephrase this question for my own understanding:

The language $L = \{w \in \{a, b\}^∗ \mid \ |w|_a = |w|_b\}$ is the language of all words (henceforth strings) generated by the regular expression $(a \ \cup \ b)^*$ such that the length of the substring of a's is equal to the length of the substring of b's.

secondly, I try and reconcile the question with what I know:

It was suggested that the equivalence classes that I am trying to determine are $a^n, b^n$.

So, I think that the equivalence classes could be listed like so: $[\varepsilon], [a], [b], [ab], [aabb], \dots , [a^n][b^n]$ since all of these strings could be concatenated with some substring z and be an element of the given language.

But, coming back to the question, I have not fulfilled the determination part of the task. So, if anyone could help me validate my reasoning and formalize a solution, I would be very grateful.

Thanks in advance.

  • $\begingroup$ Which equivalence are you referring to? The Nerode equivalence, or the syntactic congruence? $\endgroup$
    – J.-E. Pin
    Jun 28, 2019 at 13:50
  • $\begingroup$ @J.-E.Pin apologies- Nerode equivalence $\endgroup$
    – Jackie
    Jun 28, 2019 at 18:16

1 Answer 1


It's most natural to (try to) follow the definitions of $\approx_L$ you know, to simplify what these "tell" for your specific $L$. First let's recall a couple of these.

Given an alphabet $\Sigma$, and $L\subseteq\Sigma^{\ast}$, $\approx_L$ is defined by $$u\approx_L v\iff(\forall w\in\Sigma^{\ast})\ (uw\in L)\Leftrightarrow(vw\in L)\qquad(u,v\in\Sigma^{\ast})$$ (it's what I see "almost everywhere") or, alternatively, by $$u\approx_L v\iff u^{-1}L=v^{-1}L,\qquad u^{-1}L:=\{v\in\Sigma^{\ast} : uv\in L\}$$ (here, $u^{-1}L$ is just a denotion). The latter may be easier to work with, and is particularly useful because an equivalence class w.r.t. $\approx_L$ consists of (all) $u\in\Sigma^{\ast}$ having the same set $u^{-1}L$.

So, instead of trying to (simplify and) understand what $u\approx_L v$ means (again, for your specific $L$), one may try to see what each $u^{-1}L$ looks like, and for which $u$ it does so. (A hint to start, if relevant: each $u^{-1}L$ is a set of all words with a fixed difference of the numbers of $a$'s and $b$'s. If this hint is understood, it's just a small step behind the answer.)


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .