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 NEQUIVPDACFG is recognizable. Remark: Although this language is recognizable, it is not decidable. Hint: Use the fact that (M,G) E NEQUIVPDA,CFG iff L(MAL(G) # 0, 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 NEQUIVPDACFG is recognizable. Remark: Although this language is recognizable, it is not decidable. Hint: Use the fact that (M,G) E NEQUIVPDA,CFG iff L(MAL(G) # 0, where denotes the symmetric difference