4 votes 4 votes If L1 = { anbncm | n.m >0 } L2 = { anbmcm | n, m > 0} Which of these following are false? 1) L1 ∩ L2 is CFL. 2) L1 ∪ L2 is CFL. 3) L1 and L2 are CFL. 4) L1 ∩ L2 is CSL. I think (1) is FALSE as L1 ∩ L2 becomes CSL. PLease correct me if iam wrong. Theory of Computation theory-of-computation dcfl closure-property + – AnilGoudar asked Jun 5, 2017 AnilGoudar 1.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes L1 = CFL // string matching is task of CFL , one stack is enough L2 = CFL // same logic L1∩L2 = anbncn // two stack needed for this so CFL can't do this so it's CSL L1∪L2 =CFL // CFL close under union Rupendra Choudhary answered Jun 5, 2017 Rupendra Choudhary comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments iarnav commented Nov 2, 2017 reply Follow Share @Rupendra Choudhary Sir, may you please explain how L1 ∩ L2 = anbncn How this intersection is being taken and how all a,b,c get same power n. I'm so confused in this. 1 votes 1 votes Rupendra Choudhary commented Nov 2, 2017 reply Follow Share L1∩L2 means set of strings that support the property of L1 as well as L2 L1 language is set of strings that contains same number of a and b and a is followed by b , there is no bound on number of c but b must be followed by c. like L1 ={abcn ,aabbcn,aaabbbcn ,aaaabbbbcn........} //n>0 L2 language is set of strings that contains same number of b and c and b is followed by c and there is no bound on number of a but a must be followed by b. like L2={anbc,anbbcc,anbbbccc,anbbbbcccc.....} // n>0 when we talk about strings that support both L1 and L2 property , we can see a) a must be followed by b and b must be followed by c. Now the point is number of those a,b,c. it's like transitive relation # a =#b and (and because it's intersection)#b=#c so eventually #a=#c if i say L1∩L2 contains string abbcc , can you check it's true or not? see here this string not supporting claim of L1 , which says #a=#b hope you got it... PS : arnav i'm more comfortable with Rupendra or say brother :) 3 votes 3 votes iarnav commented Nov 3, 2017 reply Follow Share Thank you so much, R! 0 votes 0 votes Please log in or register to add a comment.