decidability

Question

S = { <M> | M is a DFA that accepts some palindrome }. Then what will be S -

a) Turing recognizable

b) decidable

c) undecidable

d) none of these

Answer 1

It is decidable I guess, not sure
give the palindrome and check if it reaches the final state.if it reaches then its the correct dfa else not

Comments

@Surabhi Kadur

how you will know it ?...if you really knew it, than what was the need of qsn, it will always be decidable.

---

it is decidable, you can prove like this,

1-make PDA for palindromic strings and find corresponding CFG L_C

2-find language for given DFA, say it L_R

3-find L_final = L_R intersection L_C, which will also be CFG

4-check if L_final is empty

5- if empty your dfa does not accept any palindrome else your dfa accept some palindrome

steps 1 to 5 are all decidable because we have algorithm for each steps, so finally this qsn " M is a DFA that accepts some palindrome ?" is decidable

---

Thanks

Answer 2

Answer: B

A language is Decidable if there is a Turing Machine which will accept strings in the language and reject strings, not in the language. It will hault. So, not turing recognizable.