Rigorously

Rigorously establish the decidability or undecidability of the following languages: (a) (20 Points) L = the decimal expansion of p = 3.14 . . . contains n (or more) consecutive 0’s. (b) (20 Points) L = D is a DFA and L(D) is not recognized by a DFA with fewer states. 2. (30 Points) Prove that the following language is undecidable by giving a reduction from the Post Correspondence Problem. L = G is a CFG and L(G) contains at least one palindrome. 3. (30 Points) Let A be any language in P over the alphabet 0, 1. Prove that LA = n ? N, A n 0, 1 n 6= Ø