ItsAcademics

1) a. If L 1 and L 2 are context free languages then show that L 1 U L 2 , L 1 - L 2 , L 1 ꓵ L 2 are closed or not. i)                     L 1 U L 2    If L 1 and L 2 are context free languages then there exists a context-free grammar   G 1 = (V 1 ,Σ 1 , R 1 ,S 1 ) and G 2 = (V 2 ,Σ 2 ,R 2 ,S 2 ) such that L 1 =L(G 1 ) and L 2 =L(G 2 ). We will build a new grammar G such that L(G)=L(G 1 ) U L(G 2 ). G will contain all the rules of both G 1 and G 2 .   We add to G a new start symbol S and two new rules. S→S 1 and S→S 2 . The two new rules allow G to generate a string iff at least one of G 1 or G 2 generates it. So, G = ( V 1 U V 2 U {S}, Σ 1 U Σ 2 , R 1 U R 2 U {S→ S 1 ,S→S 2 }, S ) Therefore, the context-free languages are closed under union ii)                   L 1 - L 2 Given language L 1 , ￢ L 1 =Σ*- L 1 and L 2 , ￢ L 2 =Σ*- L 2 Σ * is context-free So, if the context-free languages were closed under difference, the complement of any CFL wou