# What is the complement of ACFG

What is the complement of $\mathrm{ACFG} = \{ G \mid G \text{ is a CFG and }L(G) = \Sigma^* \}$?

I think it is $\mathrm{ECFG} = \{ G \mid G\text{ is a CFG and }L(G) = \emptyset \}$.

It makes sense to me because the complement of the empty language is the universal language?

Am I correct?

• Do you know the rule of De Morgan? If $A = \{ x \in X \mid P(x)\}$ then $\overline{A} = \{ x \in X \mid \lnot P(x)\}$. You did not invert $P$ correctly, and you don't state $X$. – Raphael Mar 20 '15 at 7:08
• @Raphael This is not really an instance of De Morgan, though certainly De Morgan's rules are good to know. – Yuval Filmus Mar 20 '15 at 11:04
• @YuvalFilmus In this particular case here, $P$ is of the form $A \land B$ so I think De Morgan's rule is (aside from the definiton I cite) all that's needed. – Raphael Mar 20 '15 at 11:11
• @Raphael Fair enough. – Yuval Filmus Mar 20 '15 at 11:11

The complement of a set $A$ given a universal set $U$ is defined as the set of elements in $U$ but not in $A$; it is understood that all elements in $A$ are also in $U$. So if $U$ is the set of all context-free grammars, then the complement of ACFG is the set of all context-free grammars $G$ such that $L(G) \neq \Sigma^*$. If $U$ is the set of all grammars then the complement of ACFG is slightly more complicated: it consists of all non-context-free grammars together with all context-free grammars $G$ such that $L(G) \neq \Sigma^*$.
If $G$ is a context-free grammar and $L(G) = \emptyset$ then $G$ certainly belongs to the complement of ACFG1; but other context-free grammars also belong there.
1This actually depends on your definition of grammar and on the value of $\Sigma$. If $\Sigma$ is understood and non-empty then what I wrote is correct; if $\Sigma$ is part of the grammar and is always non-empty, again what I wrote is correct; but if $\Sigma$ could be empty, then $\Sigma^* = \emptyset$, so what I wrote is wrong.