Grade up topicwise questions

Question

L1={a^n b^n c ^m|m>=0 and n>=0}

L2={a^m b^ n c^ n|n>=0 and m>=0}

If L3=L1UL2 then how many of L1,L2,L3 are context free languages?

A)1 (B)2 (C)3 (D) none

Answer given option C.

Please explain?

Comments

In L1, we can compare a number of a's with a number of b's and L2 we can compare a number of b's with the number of c's by a stack, so both are CFL and we know that CFL is closed under union operation, So L3 is also CFL.

Hence, L1, L2 and L3 are CFL...

Answer 1

Answer is C.



Explaination:

L1 is Context Free Language as We can construct a PDA for it easily. Push 'a' then pop 'a' for every 'b' and no need to consider  'c'.

L2 is also Context Free Language. Dont consider 'a'. Push 'b' and pop 'b' for every 'c'.

L3 is also context Free as CFL is closed under Union, Concatenation And Kleene Closure.

As L2 and L3 are CFL. L1 will be CFL.

Comments

Nice explanation. My doubt is clear now.

Answer 2

CFL is closed under union .