0 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 ? Theory of Computation + – dnivara 524 views answer comment Share Follow Print See all 3 Comments 3 3 Comments reply Mk Utkarsh commented Dec 10, 2018 reply Follow flag CFL's are not closed under complementation 1 1 replyShare smsubham commented Dec 10, 2018 reply Follow flag Its not closed. https://gatecse.in/closure-property-of-language-families/ 0 0 replyShare parabol commented Dec 11, 2018 reply Follow flag 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 1 replyShare Please log in or register to add a comment.
