2
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ Maybe this question would be better off on cs.SE. $\endgroup$
    – Raphael
    Jun 12, 2012 at 8:16

1 Answer 1

6
$\begingroup$

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}$.

$\endgroup$
2
  • $\begingroup$ Do you need to worry about the case where no transition is defined in the initial PDA? In that case, I think you would need to have some new transition defined that would keep the PDA alive long enough to reach an accepting state. I think it's always possible to do this, in which case this is a really great answer. $\endgroup$ Jun 12, 2012 at 20:57
  • $\begingroup$ Another standard way is parity (which yields $\oplus P$ for TMs); and there can be several ways in alternating machines. A small difference is that majority, bounded majority and parity are well-defined only when there is a finite number of branches, while an accepting computation of a PDA can be arbitrarily long. $\endgroup$
    – sdcvvc
    Jun 14, 2012 at 0:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .