retagged by
525 views
0 votes
0 votes
Why the complement of a CFL is CSL?
retagged by

1 Answer

2 votes
2 votes

Since CFL is not closed under complement so we can just push it above (promote it) to be a CSL. This is because Context sensitive languages (CSL) are closed under union, intersection, complement, concatenation, kleene star, reversal. Now, CSL in turn is a subset of recursive languages. Hence CFL complement is also REC.

edited by

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
0 answers
3
1 votes
1 votes
1 answer
4
practicalmetal asked Mar 20, 2023
358 views
The complement of the languages:i) {ww | w in (0+1)*}ii) {$a^n b^nc^n$ | n>1} area) Context Free b) Not Context Free c)are DCFL’s d)None