Problem 6. [20 points) Recall that a string is a palindrome if it is equal to its reverse. 1. Show that the following problem is decidable: Given a DFA A, determine whether its language L(A) contains some string that is a palindrome. That is, there is an algorithm that decides the language { A is a DFA and Swe L(A) such that w is a palindrome). Describe your algorithm at a high level; you do not need to give a Turing machine description. (Hint: Show first that for every DFA A, the language w we L(A) and w is a palindrome) is context-free.) 2. Show that the language { G is a context-free grammar and we L(G) such that w is a palindrome is undecidable. (Hint: Problem 1 of Homework 6 may be useful here. One way is to reduce from the language { A is a DFA and Swe L(A) such that w is a palindrome). Describe your algorithm at a high level; you do not need to give a Turing machine description. (Hint: Show first that for every DFA A, the language w we L(A) and w is a palindrome) is context-free.) 2. Show that the language { G is a context-free grammar and we L(G) such that w is a palindrome is undecidable. (Hint: Problem 1 of Homework 6 may be useful here. One way is to reduce from the language {