I just not sure does empty set have a context-free grammar in Chomsky normal form?
That is, for $B=\emptyset$, then a context-free grammar is $S \to S$, I think which doesn't have a Chomsky normal form. I am not sure. Can some one explain?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ If your set of production rules is empty, you cannot derive a single word with the grammar, hence its language is $\emptyset$. $\endgroup$– A.SchulzCommented Jul 12, 2013 at 11:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Note that every context-free language has a grammar in CNF (that is proven) and $\emptyset$ is context-free, so the answer is clearly: yes!
Do you get from $S \to S$ to it, using the normal transformation algorithm? No, because the usual algorithm requires a reduced, chain-rule free grammar as input; yours does not fit.
Approach one: use the algorithms (from lecture or textbook) to remove the chain rule, and try again!
Approach two: start with another grammar that fulfills the criteria!
Approach two is doomed to fail for most grammars: in order for a grammar to derive not a single word, it can not have any rules that are not thrown out by reducing. Thus, the only (kind of grammar) that works is $(\{S\}, \Sigma, \emptyset, S)$, that is a grammar with no rules at all. Note that it is in CNF.