CMI 2021 Computer Science (A2)

Question

Let L be the language over {a, b} that contains the same number of occurrences of a
and b. Which of the following languages is regular?
(a) L ∩ a∗b∗
(b) (L ∩ a∗b∗) ∪ a∗b∗

(c) L ∪ a∗b∗
(d) (L ∩ a∗b∗) ∪ b∗a

My personal doubts :( Sorry, this somewhat will reveeal the answer but I am a little confused )

Could someone please explain  ( c ) and ( d ) ?
I have posted their official answer below as well.

 

One more thing, RL are closed under union, intersection.

L 1= a*b*  is regular and and L is regular.

However L1 union/intersection L is not regular … Could someone please explain this question in some detail ?

Comments

can you make equivalent finite-state automaton for L if it is regular ?

---

Yes, you can have a DFA for regular languages.

---

you can’t make DFA for L because it is not regular. You can prove it by pumping lemma or based on the statement of option (a) as you have also said in your question.

$L\; \cap a^*b^* =\{a^nb^n: n\geq 0\}$

Since, $\{a^nb^n: n\geq 0\}$ is not regular and intersection of two regular languages is regular. So, if $L$ is regular then $L\; \cap a^*b^*$ which is $\{a^nb^n: n\geq 0\}$ should also be regular but it doesn’t. So we have reached at a contradiction which shows that $L$ is not regular.

Answer 1

This is the official answer ;

A\
       

Answer: (b) (L ∩ a∗b∗) ∪ a∗b∗
(a) L ∩ a∗b∗ = {anbn | n ≥ 0} is not a regular language.
(b) (L ∩ a∗b∗) ∪ a∗b∗ = {ambn | m, n ≥ 0} is a regular language.
(c) If L3 = L ∪ a∗b∗ were regular, then L3 ∩ b∗a∗ would also be regular. But L3 ∩ b∗a∗
is {bnan | n ≥ 0}, which is not regular.
(d) If L4 = (L ∩ a∗b∗) ∪ b∗a∗ were regular, then L4 ∩ a∗b∗ would also be regular. But
L4 ∩ a∗b∗ is {anbn | n ≥ 0}, which is not regular.

\