1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Raphael Mar 20 '15 at 7:08
  • $\begingroup$ @Raphael This is not really an instance of De Morgan, though certainly De Morgan's rules are good to know. $\endgroup$ – Yuval Filmus Mar 20 '15 at 11:04
  • $\begingroup$ @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. $\endgroup$ – Raphael Mar 20 '15 at 11:11
  • $\begingroup$ @Raphael Fair enough. $\endgroup$ – Yuval Filmus Mar 20 '15 at 11:11
3
$\begingroup$

First of all, the complement of a set is only defined when there is an (understood) universal set. In this case, the universal set is probably the set of all context-free grammars, but it could plausibly be the set of all grammars.

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.

$\endgroup$
  • $\begingroup$ So If U is the set of all context free grammars, then complement of AFCG is the language of ∅? Can I say that this statement is true under that condition : (the complement of AFCG is EFCG). $\endgroup$ – blazedforce123 Mar 20 '15 at 6:49
  • $\begingroup$ No, try to read my answer again. $\endgroup$ – Yuval Filmus Mar 20 '15 at 6:49
  • $\begingroup$ Ah I understand now, EFCG (the empty set) belongs to the complement of AFCG but so do all the other CFG G such that L(G) ≠ Σ∗. Thus then complement to AFCG is CFG B = {B | B is a CFG and L(B) ≠ Σ∗} ? $\endgroup$ – blazedforce123 Mar 20 '15 at 6:54
  • $\begingroup$ Right, you got it now. $\endgroup$ – Yuval Filmus Mar 20 '15 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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