logiccomputer-scienceautomatafinite-automatanon-deterministic

Complement of non-deterministic context-free language


The complement of a context-free language is not always context-free. It is not allowed to just swap the final and non-final states of an NPDA and assume that it produces the complement of the language. Could someone give an example where it goes wrong? And why does the above described procedure work for regular languages given a DFA? Maybe because DFA and NFA are equivalent and DPDA and NPDA are not?


Solution

  • Well, swapping the final vs non-final states of an NFA doesn't even guarantee you'll get the complement of the language. Consider this rather curious NFA:

    ----->q0--a-->[q1]
          |
          a
          |
          V
          q2
    

    This NFA accepts the language {a}. Swapping the final and non-final states, the accepted language becomes {e, a}. These languages are not complementary since they have an intersection.

    In exactly the same way, swapping the states of a NPDA is not guaranteed to work either. The difference, as you point out, is that for any NFA, there is some equivalent DFA (indeed, there are lots), and swapping toggling the finality of states will work for those, so the languages are guaranteed to be closed under complementation.

    For NPDAs, though, we do not necessarily have equivalent DPDAs (where swapping finality would work fine). Thus, it is possible that the complement of some languages accepted only by NPDAs is not context-free.

    Indeed, the context-free language {a^i b^j c^k | i != j or j != k} is accepted only by NPDAs and its complement {strings not of the form a^i b^j c^k or strings of that form with i=j=k) is not context-free.