2. [10 points] Consider the problem of determining whether a PDA and a CFG are not equivalent. (a) Express this problem as a language NEQUIVPDA CFG (b) Show that NEQUIVpDA.CFG is recognizable. Remark: Although this language is recognizable, it is not decidable. Hint: Use the fact that M,C) NEQUIVPDA,CFG iff L(M)AL(G) # , where denotes the symmetric difference 2. [10 points] Consider the problem of determining whether a PDA and a CFG are not equivalent. (a) Express this problem as a language NEQUIVPDA CFG (b) Show that NEQUIVpDA.CFG is recognizable. Remark: Although this language is recognizable, it is not decidable. Hint: Use the fact that M,C) NEQUIVPDA,CFG iff L(M)AL(G) # , where denotes the symmetric difference