in Theory of Computation retagged by
219 views
0 votes
0 votes
Why the complement of a CFL is CSL?
in Theory of Computation retagged by
by
219 views

1 comment

CFL’s are strict subset of CSL and CSL’s are closed under complementation so CFL complement are CSL.
1
1

1 Answer

1 vote
1 vote

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

1 comment

Just to add complement of a CFL can also be regular but this is not true for EVERY CFL.
2
2

Related questions