CMI2019-A-1

Question

Let $L_{1}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m\geq n\}$ and  $L_{2}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m < n\}.$
The language $L_{1}\cup L_{2}$ is:

• A. regular, but not context-free
• B. context-free, but not regular
• C. both regular and context-free
• D. neither regular nor context-free

Comments

Union of L1 and L2 will give language containing 'a' followed by 'b'

---

Option C is correct.

Answer 1

$L_1$ contains set of all strings of the form $(a...b...)$ where number of $b'$s should be greater than or equal to $a'$s

i.e. $L_1 = \{ \epsilon , b ,bb, bbb...., ab, abb , abbb, .....,aabb, aabbb..... \}$

$L_2$ contains set of all strings of the form $(a...b...)$ where number of $b'$s should be strictly less than $a'$s

i.e. $L_2 = \{  a ,aa, aaa...., aab, aaab, aaabb , aaaab, aaaabb, aaaaabbb, .....\}$

 
So when we do union of both $L_1$ and $L_2$ then we will get a language in which

Either (number of $b'$s should be greater than or equal to $a'$s) OR (number of $b'$s should be strictly less than $a'$s)

i.e. $L_1 \cup L_2 = \{ a^nb^m | n,m \geq 0\ and\ m \geq n \ OR\ m < n \} $

i.e. We can have any number of $a's$ followed by any number of $b'$s

i.e. $ L_1 \cup L_2= \{ a^nb^m | n , m \geq 0 \}$

 This is a regular language since we can draw a finite automata for it.

And as we know every regular language is also a context free language .

$\therefore$ Option $C.$ is the correct answer.

Comments

option c is correct

---

@Satbir @Lakshman Patel RJIT   @soujanyareddy13 

If we consider individual language i.e. only L1 and L2 then aren’t both context sensitive language as both will require atleast 2 stacks ?

Answer 2

Comments

@Satbir @Lakshman Patel RJIT   @soujanyareddy13 

If we consider individual language i.e. only L1 and L2 then aren’t both context sensitive language as both will require atleast 2 stacks ?

Answer 3

This question is one of the good examples of knowing where not to apply closure property to get the answer.

 Both are DCFL, since DCFLs are not closed under union operations, so let’s upgrade it to CFL and since CFL are in fact closed under union operation, we stop and say the result must be a CFL.  And a CFL need not be regular,so it seems option B is right but here we need to be careful, since it is MCQ, we have to be very cautious while choosing an option.

When we do actual union of the language, we will see it generates a*b* which is in fact regular, and a regular is always a CFL,so option C is right