# Let $L$ the language over $\{a,b\}$ of words that contains the same number of occurrences of $a$ and $b$. Which of the following languages is regular?

The options are:

(a) $$L \cap a^{\ast}b^{\ast}$$

(b) $$(L \cap a^{\ast}b^{\ast}) \cup a^{\ast}b^{\ast}$$

(c) $$L \cup a^{\ast}b^{\ast}$$

(d) $$(L \cap a^{\ast}b^{\ast}) \cup b^{\ast}a^{\ast}$$

My doubt is: We don't know what exactly $$L$$ is, it could be $$a^{n}b^{n}$$ or $$b^{n}a^{n}$$, we for sure know that $$L$$ is either of the two!

The way I think is, when we look at the first option the resultant language can be either $$\epsilon$$ or $$a^{n}b^{n}$$ because $$L$$ can be either of the mentioned choices, which also means that we can't deduce it properly, similarly i cannot decipher the other options.

Can someone explain why each option is either correct or wrong choice? Given that the correct option is $$(b)$$

• "We don't know what exactly L is, it could be $a^nb^n$ or $b^na^n$, we for sure know that L is either of the two!" > I don't understand this sentence. $a^nb^n$ and $b^na^n$ are words, not languages. And even if you meant $\{a^nb^n\mid n\geqslant 0\}$, this is not equal to $L$. $L$ contains all words with the same number of $a$'s and $b$'s, like $a^nb^n$ for any $n$, but also $b^na^n$, but also $abababab…$, but also $aabbbbaa$, … Commented Apr 8, 2023 at 10:14
• @Nathaniel Oh that's true! I did think of that but somehow convinced myself otherwise but now that you have re-stated it in a clear format, i agree $L$ can be any of the langauges you mentioned. And yes i meant langauges as you said! Do you know how to further deduce the solution? Commented Apr 8, 2023 at 10:23

(b) is the only correct answer and this follows directly from the well known proof, $$L_1 = \{a^n b^n : n \in \mathbf{N}\}$$ is not regular. You can refer to the second page of this resource, for example.
(a) We start of by noting that $$L' = L \cap a^*b^*$$ is equivalent to $$L_1$$, which is not regular.
(b) $$L_1 \cup a^*b^*$$ is equivalent to $$a^*b^*$$ which is regular. This can be easily verified by constructing a single state automaton accepting any number of $$a$$s and $$b$$s.
(c) We prove this using pumping lemma. Let $$x = b^na^n$$. Clearly, $$x \in L', |x| \geq n$$.
Let $$uv = b^j$$ for some $$j \in \mathbf{N}, 0 \leq j \leq n, v = b^k$$ for some $$k \in \mathbf{N}, 0 < k \leq n$$.
If $$L'$$ was regular, then $$uv^2w = b^{n+k}a^n \in L'$$, which is not true. Thus, $$L'$$ is not regular.
(d) Here, $$L' = a^nb^n \cup b^*a^*$$. Apply the same proof as in (c) for the string $$x = a^kb^k, k \in \mathbf{N}$$.