1 votes 1 votes If a language L is Context Free Language then what can we say about $L^-$ (Complement of L): 1. It is surely not Context Free Language? 2.It may or may not be Context Free Language? Theory of Computation theory-of-computation context-free-language + – Manish Chetwani asked Sep 14, 2017 Manish Chetwani 329 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Arjun commented Sep 14, 2017 reply Follow Share What is the "contradiction"? The one you posted also will be given in any standard TOC textbooks -- I still remember the sentence "If a language and its complement are r.e., then it must be recursive". Even the proof for this is given in Ullman -- or any standard textbook. 0 votes 0 votes Manish Chetwani commented Sep 14, 2017 reply Follow Share Actual Answer is given as b in the book from which I was solving. I was thinking that if it is given in question that it is not Recursive then complement of the Language may be recursive or may not be right? It is not sure that it is not recursively enumerable 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes Closure property only tells us about the class of language when it holds for that class of language..If the property does not hold , it may or may not belong to that class.. Hence complement of a CFL may or may not be CFL.. Habibkhan answered Sep 14, 2017 selected Sep 14, 2017 by Arjun Habibkhan comment Share Follow See 1 comment See all 1 1 comment reply Manish Chetwani commented Sep 14, 2017 reply Follow Share @Habibkhan Thanks Sir!! 0 votes 0 votes Please log in or register to add a comment.