The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
120 views
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.2k points) | 120 views
0
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.



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

CFL is closed under union .

answered by Boss (23.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

40,903 questions
47,560 answers
146,294 comments
62,306 users