The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes
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?
asked in Theory of Computation by Active (1.1k points) | 63 views
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...

2 Answers

+3 votes
Best answer
Answer is C.


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.
answered by (129 points)
selected by
Nice explanation. My doubt is clear now.
+3 votes

CFL is closed under union .

answered by Boss (12.9k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,518 questions
42,792 answers
42,162 users