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 ?
2026-03-29 17:25:28.1774805128
If a language is context free ,then why is the complement of the language recursively enumerable?
3k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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