3 votes 3 votes Suppose in question we are given the language is Turing Decidable , can I consider it a CFL or Regular? Theory of Computation theory-of-computation regular-language decidability turing-machine + – Parshu gate asked Nov 29, 2017 Parshu gate 611 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Red_devil commented Nov 29, 2017 reply Follow Share well a Turing decidable language is Recursive. 0 votes 0 votes prateekdwv commented Nov 29, 2017 reply Follow Share No, you can only consider it to be recursive and there must exist a halting Turing machine that will accept that language. However, it might not be acceptable by any pushdown automata and for that matter by a finite automaton as well. 0 votes 0 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes turing decidable means it is a recurcive language and a recurcive language may or may not be cfl or regular. abhishekmehta4u answered Apr 23, 2018 selected Apr 26, 2018 by Arjun abhishekmehta4u comment Share Follow See 1 comment See all 1 1 comment reply pps121 commented Dec 8, 2018 reply Follow Share so which is TRUE: 1)All recursive lang are decidable problems? 2)All decidable problems are recursive language? - is both of them are true? any proof please? 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes A Turning Decidable language is Recursive. Since the group of recursive languages is larger when compared to regular and cfl , the language may not necessarily be regular or CFL . Jeevesh answered Nov 29, 2017 Jeevesh comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes All regular, context free and context sensitive languages are recursive or turing decidable. But vice versa is not true. For example anbncn n>1 is recursive (more precisely its CSL) but its not context free. ♥_Less answered Nov 29, 2017 ♥_Less comment Share Follow See all 0 reply Please log in or register to add a comment.