0 votes 0 votes Can we claim that a CFL is closed under complementation by transforming it’s NPDA in a way such that it’s non-final states become final states and final states become non-final ? dnivara asked Dec 10, 2018 dnivara 221 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Mk Utkarsh commented Dec 10, 2018 reply Follow Share CFL's are not closed under complementation 1 votes 1 votes smsubham commented Dec 10, 2018 reply Follow Share Its not closed. https://gatecse.in/closure-property-of-language-families/ 0 votes 0 votes parabol commented Dec 11, 2018 reply Follow Share There is proof that, if you do complement operation on a CFL result might not be a CFL (sometimes it result in CFL,but not always ,for eg : regular languages are CFL whose complement is regular ,ie CFL) The method you suggested only works with DFA. Here , if you follow this method, result will be a NPDA, but it might not be the NPDA for the complement of the language. 1 votes 1 votes Please log in or register to add a comment.
