Cheap and Secure Web Hosting Provider : See Now

[Answers] What is the complement of ACFG

, , No Comments
Problem Detail: 

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?

Asked By : blazedforce123

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40585

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback