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?

  • 4
    $\begingroup$ 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$. $\endgroup$ – Shaull Oct 15 '20 at 8:41
  • $\begingroup$ 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. $\endgroup$ – oldsailorpopoye Oct 15 '20 at 8:46
  • $\begingroup$ Perhaps you can answer your own question? $\endgroup$ – 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.


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.