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) difference. NEQUIVPDA,CFG iff L(MAL(G) 0, where denotes the symmetric Basically, yes. But NEQUIV_PDA,CFG) is the name of a language that expresses this concept, just as EQ_DFA (on the top of page 197) is the name of a language that expresses the concept of two DFAs being equivalent. 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) difference. NEQUIVPDA,CFG iff L(MAL(G) 0, where denotes the symmetric Basically, yes. But NEQUIV_PDA,CFG) is the name of a language that expresses this concept, just as EQ_DFA (on the top of page 197) is the name of a language that expresses the concept of two DFAs being equivalent