# Determine the equivalence classes $\approx_L$ for the language $L = \{w \in \{a, b\}^∗ \mid |w|_a = |w|_b\}$

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.

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

## 1 Answer

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.)