611 views
3 votes
3 votes
Suppose in question we are given the language is Turing Decidable , can I consider it a CFL or Regular?

3 Answers

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.

selected by
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 .
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.

Related questions

1 votes
1 votes
2 answers
1
Parshu gate asked Nov 29, 2017
827 views
Suppose in question we are given the language is Turing Recognizable , can I consider it a CFL or Regular?