# Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?

Is $$L = \{ w : \#_a(w) = \#_b(w) \}$$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular.

If we assume on the contrary, then there exists a pumping length $$p$$. In that case, the word looks like $$xyz$$ where $$|xy| \leq p$$. If $$y$$ does not have the same number of $$a$$'s and $$b$$'s then $$xy^iz$$ for $$i>1$$ will give us a contradiction. Otherwise $$y$$ has the same number of $$a$$'s and $$b$$'s. This does not lead me to anywhere. I tried creating cases where this would fail -- seems like there isn't any.

This link answers it, but I do not understand what they mean by "a regular language is one that uses finite memory". I have encountered similar reasoning before, I have not been able to figure it out.

This answer seems to check if a number satisfies the criteria using regex. Is that a different form of regex?

• Recall that regular languages are closed under intersection, and that $a^*b^*$ is regular. Can you use that to prove that the language is not regular? Alternatively, recall that for the pumping lemma, you can choose the word $w$ you work with. Try words of the form $a^pb^p$. – Shaull Oct 15 '20 at 8:41
• Makes sense. In $a^p b^p$, we have $xy = a^{p-k}$ for some $k \geq 0$. That does the job, since $y^{i}$ for $i>1$ adds more $a$'s. Even $i^0$ gives us a contradiction. – oldsailorpopoye Oct 15 '20 at 8:46
• Perhaps you can answer your own question? – Yuval Filmus Oct 15 '20 at 10:48

This can also be proved easily using Myhill-Nerode theorem.

Myhill-Nerode Theorem: Given a language $$L \subseteq \Sigma^*$$, Suppose $$\forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^* ,L(xz) \neq L(yz))$$ where S is an infinite set. Then L is not a regular language.

(Here $$L(w) = 1$$ if $$w \in L$$ and $$L(w) = 0$$ if $$w \notin L$$.)

For the given problem, We have $$L=\{w:\#_a(w)=\#_b(w)\}$$.

Take $$S = a^*$$ (note: the set $$S$$ is infinite).

Now take any two distinct elements from set $$S$$, $$x=a^i$$ and $$y=a^j$$, and take $$z=b^i$$.

So $$xz \in L$$ and $$yz \notin L$$.

Hence, we will get an infinite number of distinct quotients as $$S$$ is an infinite distinctive set.

Thus, $$L$$ is not regular.

Use the pumping lemma: If $$L$$ is regular, there is a constant $$N \ge 1$$ such that any string $$\sigma \in L$$ can be divided as $$\sigma =\alpha \beta \gamma$$ with $$\lvert \alpha \beta \rvert \le N$$, $$\beta \ne \varepsilon$$ so that for all $$k$$ the string $$\alpha \beta^k \gamma \in L$$.

Proof is by contradiction. Assume your $$L$$ is regular, let $$N$$ be the lemma's constant and pick $$\sigma = a^N b^N \in L$$, $$\lvert \sigma \rvert = 2 N \ge N$$. You see that $$\alpha \beta$$ is just 'a', so leaving out $$\beta$$ (i.e., $$k = 0$$) destroys the balance between 'a' and 'b', the result is not in $$L$$. Contradiction.