Let L = { | G is a context-free grammar (CFG) such that L(G) contains at least one palindrome}. Show that L is undecidable by a reduction for PCP (the Post Correspondence Problem). Write down a CFG G such that L(G) contains a palindrome if and only if a given PCP P = {[t_1/b_1], [t_2/b_2] ..... [t_k/b_k]} has a solution. Assume t_i, b_i sum {0, 1}*. Argue that your grammar G has the desired property of (a) Let L = { | G is a context-free grammar (CFG) such that L(G) contains at least one palindrome}. Show that L is undecidable by a reduction for PCP (the Post Correspondence Problem). Write down a CFG G such that L(G) contains a palindrome if and only if a given PCP P = {[t_1/b_1], [t_2/b_2] ..... [t_k/b_k]} has a solution. Assume t_i, b_i sum {0, 1}*. Argue that your grammar G has the desired property of (a)