edited by
13,218 views
13 votes
13 votes
the complement of every context-free language is recursive ? or recursive enumerable? or both?
edited by

5 Answers

Best answer
46 votes
46 votes
Both. Also, context-sensitive.

CFL is a strict subset of CSL. CSL is closed under complement. So, CFL complement is CSL.

And CSL is a strict subset of recursive which in turn is a strict subset of recursively enumerable.
selected by
12 votes
12 votes
CFL is not closed under complement. So, complement of CFL may or may not be a CFL.

CFL is a subset of CSL. And CSL is closed under complement. So, CSL complement (and hence CFL complement also) is always guaranteed to be a CSL (hence recursive also).
1 votes
1 votes
Complement of recursive language is recursive, since all the context free languages are recursive, complement of context free language should also be recursive.

Since all recursive enumerable languages are recursive, complement of CFL is both recursive and recursive enumerable.
0 votes
0 votes
if grammer is regular then ans is change...because reg is also cfl

Related questions

0 votes
0 votes
2 answers
2
1 votes
1 votes
1 answer
3