2

If a language is CFL , then it is clearly recursive and if it is recursive then it is obviously recursively enumerable but then recursively enumerable languages are not closed under complement so how can we prove the above statement is true ?

RADHA GOGIA
  • 197
  • Certainly some recursively enumerable sets have recursively enumerable complements, just not all. – Noah Schweber Nov 20 '15 at 09:44
  • But we have to tell whether this statement is true or false so it has to be a universal solution – RADHA GOGIA Nov 20 '15 at 09:45
  • I don't understand your comment - what do you mean a "universal solution?" CFLs are recursive. CFLs, therefore, are r.e. and have r.e. complements. Meanwhile, some r.e. sets - not CFLs, but different ones - do not have r.e. complements. What is missing? – Noah Schweber Nov 20 '15 at 09:48
  • The proof ingredient that you seem to be missing is that the complement of a recursive language is recursive. So CFL implies recursive, which implies the complement is recursive, which implies the complement is recursively enumerable. – Andreas Blass Nov 20 '15 at 10:48
  • @RADHAGOGIA, I've edited my answer. – Mithlesh Upadhyay Nov 20 '15 at 16:28

1 Answers1

2

Since, CFLs are not closed under complement property, while CSLs are closed under complement property. Every CFL is CSL , every CSL is recursive, and every recursive language is recursive enumerable language. So, complement of a CFL may not be CFL but that will be CSL sure, means, recursive as well as recursive enumerable language.

Reference@wiki

Edit : Your argument is not correct, since every recursive enumerable language may not be context free language and CFLs are subset of CSL but not every CFL is CSL.

Reference@Chomsky hierarchy

Mithlesh Upadhyay
  • 4,787