3. (15 points) It is true that context-free languages are not closed under intersection. In this problem, we will show that if L is a context-free language and K is a regular language then LnK is context-free a) Let M1 = (Q1, , 1,81,91, F1) be a PDA that recognizes L and M2 = (Q2, 2, 82, 42, F2) an NFA that recognizes K. Consider the construction of a PDA that recognizes L K N = (Q1 x Q2, 2, 7, 8, 91, 92), F1 x F2). with transition function | {[(a,b), c) | (a, c) 8((q, u, u)) and B 82(r,u)} 8((q, r), u, v) = {( (a,r),c) | (a, c) 81((q, u, v))} for q Q1,7 Q2, U 5, v El. if uts if u=5 Apply this construction to the PDA and NFA below: 0, : 0 1.0: 1,8 E, E: $ 0-0 CB 1.08 E, $ 26 b) Describe using set builder notation the language that is recognized by the PDA given in part a. (no justification necessary.) c) Describe using set builder notation the language that is recognized by the NFA given in part a. (No justification necessary.) d) Describe using set builder notation the language that is recognized by the PDA that is the result of the construction in part a. (You must describe it without using the intersection operation. No justification necessary.) e) Determine whether the resulting language from the construction is regular or non-regular. (Give a brief justification.) 3. (15 points) It is true that context-free languages are not closed under intersection. In this problem, we will show that if L is a context-free language and K is a regular language then LnK is context-free a) Let M1 = (Q1, , 1,81,91, F1) be a PDA that recognizes L and M2 = (Q2, 2, 82, 42, F2) an NFA that recognizes K. Consider the construction of a PDA that recognizes L K N = (Q1 x Q2, 2, 7, 8, 91, 92), F1 x F2). with transition function | {[(a,b), c) | (a, c) 8((q, u, u)) and B 82(r,u)} 8((q, r), u, v) = {( (a,r),c) | (a, c) 81((q, u, v))} for q Q1,7 Q2, U 5, v El. if uts if u=5 Apply this construction to the PDA and NFA below: 0, : 0 1.0: 1,8 E, E: $ 0-0 CB 1.08 E, $ 26 b) Describe using set builder notation the language that is recognized by the PDA given in part a. (no justification necessary.) c) Describe using set builder notation the language that is recognized by the NFA given in part a. (No justification necessary.) d) Describe using set builder notation the language that is recognized by the PDA that is the result of the construction in part a. (You must describe it without using the intersection operation. No justification necessary.) e) Determine whether the resulting language from the construction is regular or non-regular. (Give a brief justification.)
