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.7k 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 AnilGoudar commented Jun 5, 2017 reply Follow Share L1 is DCFL and L2 is DCFL, so L1 U L2 can't be DCFL, is it possible it can be CFL?? Please give some examples. 0 votes 0 votes Rupendra Choudhary commented Jun 5, 2017 reply Follow Share DCFL is not closed under union. yes the union of two DCFL may not be DCFL but certainly it would be CFL atleast. 2 votes 2 votes Rupendra Choudhary commented Jun 5, 2017 reply Follow Share L1 = {anbn} //DCFL L2={anb2n} //DCFL L= L1∪L2 // not DCFL but CFL yes. 0 votes 0 votes Rupendra Choudhary commented Jun 5, 2017 reply Follow Share Not closed under union doesn't mean L1∪L2 won't be DCFL , it just mean it may be DCFL or may not. close under some operation guarantee that L1∪L2 would be CFL... there may be you can find some example where DCFL union would be DCFL. 0 votes 0 votes AnilGoudar commented Jun 5, 2017 reply Follow Share @Rupendra, Can you please provide some examples where union of two DCFL is DCFL? 0 votes 0 votes Rupendra Choudhary commented Jun 6, 2017 reply Follow Share L1={a} //DCFL L2={aa} //DCFL L1∪L2 = {a,aa} //DCFL 1 votes 1 votes 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.