6 votes 6 votes 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 amrendra pal asked Aug 20, 2017 amrendra pal 1.0k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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 Surabhi Kadur answered Aug 22, 2017 Surabhi Kadur comment Share Follow See all 8 Comments See all 8 8 Comments reply amrendra pal commented Aug 22, 2017 reply Follow Share @Surabhi, language S is DECIDABLE, but can you explain more 0 votes 0 votes Surabhi Kadur commented Aug 22, 2017 reply Follow Share They have mentioned it's a DFA that accepts some palindrome ( a palindrome ) so give the input string palindrome and see if it reached final state .. 0 votes 0 votes joshi_nitish commented Aug 22, 2017 reply Follow Share @Surabhi Kadur give the palindrome and check if it reaches the final state.if it reaches then its the correct dfa else not qsn is: DFA accept some palindrome, if it reject current given palindrome doesnt mean it will not accept any other palindrome in a universe. 0 votes 0 votes amrendra pal commented Aug 22, 2017 reply Follow Share @Surabhi , i have also this doubt, please clear it, "DFA accept some palindrome, if it reject current given palindrome doesnt mean it will not accept any other palindrome in a universe". 0 votes 0 votes Surabhi Kadur commented Aug 22, 2017 reply Follow Share @joshi we will know what palindrome the Dfa accepts right ? we can give same string as input 0 votes 0 votes joshi_nitish commented Aug 22, 2017 reply Follow Share @Surabhi Kadur how you will know it ?...if you really knew it, than what was the need of qsn, it will always be decidable. 0 votes 0 votes joshi_nitish commented Aug 22, 2017 reply Follow Share it is decidable, you can prove like this, 1-make PDA for palindromic strings and find corresponding CFG LC 2-find language for given DFA, say it LR 3-find Lfinal = LR intersection LC, which will also be CFG 4-check if Lfinal 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 0 votes 0 votes Surabhi Kadur commented Aug 22, 2017 reply Follow Share Thanks 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 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. ashutoshaay26 answered Aug 27, 2017 ashutoshaay26 comment Share Follow See all 0 reply Please log in or register to add a comment.