Michael Sipser Edition 3 Exercise 4 Question 26 (Page No. 212)

Question

Let $PAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some palindrome}\}$. Show that $PAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpful here.)

Answer 1

Its is decidable because the language is Context Free and is accepted by a PDA.