0 votes 0 votes let L = “CFL but not REGULAR”, Can we get complement of L as CFL? Unlike in the case of Recursively Enumerable(RE) language where if L = “RE but not RECURSIVE”, its complement can never be RE. Theory of Computation theory-of-computation context-free-language context-sensitive + – UltraRadiantX asked Oct 9, 2021 edited Oct 9, 2021 by UltraRadiantX UltraRadiantX 450 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 3 votes 3 votes Yes, you can get a complement of language which is cfl but not regular as CFL. L={a^nb^n | n>=0} this is a cfl which is not regular.Now it’s complement L’ ={a^mb^n | m!=n} this is also a cfl. CFL’s are not closed under complementation. The complement of a CFL may or may not be CFL. raja11sep answered Oct 9, 2021 selected Oct 12, 2021 by UltraRadiantX raja11sep comment Share Follow See all 3 Comments See all 3 3 Comments reply Vishal_kumar98 commented Oct 9, 2021 reply Follow Share The language you have pointed out is a DCFL and is indeed closed under complementation. 1 votes 1 votes raja11sep commented Oct 9, 2021 reply Follow Share Yes.But is it violating his doubt? 2 votes 2 votes UltraRadiantX commented Oct 22, 2021 reply Follow Share L’ would be {a^mb^n | m!=n} U ‘ba’ as substring Since Regular union with CFL is always CFL, L’ is also a CFL. 0 votes 0 votes Please log in or register to add a comment.