A model of computation for co-CFLs?

Question

The context-free languages can be described as the languages that can be generated by a context-free grammar or recognized by a (nondeterministic) pushdown automaton.

The context-free languages are not closed under complementation, and the class co-CFL contains all languages whose complements are context-free.

Is there a model of computation (described as a grammar, automaton, generalized rewriting system, etc.) that precisely captures the co-CFLs? For example, is there a modification we can make to CFGs to have them accept precisely the co-CFLs, or some new type of automaton for them?

Thanks!

Answer 1

When defining a nondeterministc machine, you need to decide how to merge the results from the multiple computation branches into a final answer.

In general, there are (at least) 4 standard ways of doing this.

• Existential: Accept if any branch accepts. For TMs, this yields NP.
• Universal: Accept if all branches accept. For TMs, this yields coNP.
• Majority: Accept if most of the branches accept. For TMs, this yields PP.
• Bounded Majority: Same as Majority, except with the promise that either >60% or <40% of the branches accept. For TMs, this yields BPP.

CFLs are recognized by nondeterministc pushdown automata of the Existential type. Therefore, coCFLs are recognized by nondeterministic pushdown automata of the Universal type.

Formally, let $L$ be a CFL and $\bar{L}$ be a coCFL. Let $M$ be the existential pushdown automaton that accepts $L$. Construct a universal pushdown automaton $\bar{M}$ by replacing each accept state of $M$ with a reject state and each reject state with an accept state. Then $\bar{M}$ recognizes $\bar{L}$.