# There exists an algorithm to find grammar of complement of a function?

I'm wondering if there exists an algorithm to solve the following problem:

Given a grammar $$S$$ of a context-free language $$\mathcal{L}$$, find a grammar $$S'$$ such as $$L(S) = L(S')^c$$.

I note that the complement of a context-free language is also a context-free language, so the questions is well stated.

Contrary to what you wrote, context-free languages are not closed under complement. See Examples of context-free languages with a non-context-free complements for some examples. As a result, there is no such algorithm.

Also: It's decidable whether $$L(S)=\emptyset$$, but it's not decidable whether $$L(S)=\Sigma^*$$. If you could compute the complement, then you could decide the latter using the algorithm for the former.

In contrast, deterministic context-free languages are closed under complement, and the proof of that fact likely identifies an algorithm that will work when you have a deterministic context-free language. Another way to handle it: convert to a deterministic pushdown automaton, then it is clear how to complement it.

• Okay, I'm speachless now because I've been taught they were closed under complement, did't know they were talking about the deterministic context-free languages (didn't even know such thing existed). · Do you recommend any book where to find that proof? · Given a pushdown automaton how can I get the grammar by an algorithmic way? (I don't know if it's okay to ask this here or should I ask it in a different post). Sorry, I'm a newbie here. – Jay Jay Feb 16 at 2:46
• @JayJay, I learned from Hopcroft, Motwani, and Ullman. I haven't verified that it has that proof, but I'd guess it's a good bet it will. Other people have had good things to say about Sipser's book (Introduction to Theory of Computation). – D.W. Feb 16 at 4:49

Since you didn't explicitly specify that $$S'$$ should be a context-free grammar, I'll take the opportunity to mention Boolean grammars, which are a fairly modest extension of CFGs that allow conjunction and negation in rules, in addition to the implicit disjunction of CFGs. The productions have the form

$$A \to \alpha_1 \And \ldots \And \alpha_m \And \lnot\beta_1 \And \ldots \And \lnot\beta_n$$ where $$A$$ is a nonterminal, $$m+n \ge 1$$ and $$\alpha_1$$, ..., $$\alpha_m$$, $$\beta_1, \ldots, \beta_n$$ are strings formed of symbols in $$\Sigma$$ and $$N$$. Informally, such a rule asserts that every string $$w$$ over $$\Sigma$$ that satisfies each of the syntactical conditions represented by $$\alpha_1$$, ..., $$\alpha_m$$ and none of the syntactical conditions represented by $$\beta_1$$, ..., $$\beta_n$$ therefore satisfies the condition defined by $$A$$.

Then if $$G$$ is a Boolean grammar (in particular, it could be a CFG) with start symbol $$S$$, add a new start symbol $$S'$$ and add the rule $$S' \rightarrow \lnot S$$ to obtain a grammar for $$L(G)^c$$.

Boolean grammars are a "modest" extension in that the deterministic time complexity of parsing is the same as for CFGs and they can be defined by language equations, but on the other hand they recognize a much larger class of languages. For example, even conjunctive grammars do not satisfy Parikh's theorem (i.e., the conjunctive grammars over an unary alphabet recognize non-regular languages). It is an open problem whether conjunctive grammars are closed under complementation.