Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Maybe this question would be better off on cs.SE. –  Raphael Jun 12 '12 at 8:16
add comment

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
    
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. –  templatetypedef Jun 12 '12 at 20:57
    
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. –  sdcvvc Jun 14 '12 at 0:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.