edited by
969 views
3 votes
3 votes

Choose the appropriate CFL Lthat ensures $L1\bigcap L2$ is not CFL where L1={anbmcm|n,m>0)

(A)L2={anbncn|n>0}

(B)L2={anbmcp|n>m and m>p}

(C)L2={anbnc2m|n,m>0}

(D)both B and C

edited by

1 Answer

Best answer
3 votes
3 votes

I) For comparision of L1 with L2 let us rewrite L1 as : { abm cp | m = p & n,m > 0}

                                                Given        L2   as :  { abm cp | n > m & m > p }

Now the conditions m = p and m > p cannot hold simulataneosly and also n,m > 0.Hence ,

L1  ∩  L2  will be a disjoint set here.Hence a regular language hence a CFL also.So B option is false.

II) For comparision of L2 with L1 in option III) , we write L2 as : { abm cp  | n = m and p is even }

                                                       and  Las :   { abm cp | m = p & n,m > 0}

So the intersection language can be defined as   :   {an bm cp  |  n = m and m = p and p is even and n,m > 0} .In other words , we can rewrite this language as   :    L1  ∩  L2          :    { a2n b2n c2n | n > 0} which is not a CFL.It is a CSL.

III) Now coming to option a) language L2  , it can be written as : {an bm cp  |  n = m and m = p , n , m , p > 0} whereas for L1 , we have only m = p contraint and n,m > 0.Hence the intersection here results in L2 itself .Hence it is not a CFL as well.

Hence language given in option A and C both result in non CFL language after intersection.But we have to choose that option's L2 which is a CFL as well which A option dissatisfies.Hence C) option is correct as L2 is CFL here but intersection of the 2 languages is not CFL here.

selected by

Related questions

0 votes
0 votes
1 answer
1
mehul vaidya asked Sep 3, 2018
527 views
To find intersection of this two : If i proceed like thisregular ∩ CFG CFG ∩ CFG as regular lang is also CFGbut CFG is not closed under intersectionhence answer ma...
0 votes
0 votes
0 answers
2
mehul vaidya asked Aug 25, 2018
404 views
will intersection of regular and context free be always CF? I don't think so , because regular Language is also cf hence CFL intesect CFL is no always CFLref: https://gat...
1 votes
1 votes
2 answers
4