2
$\begingroup$

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?

$\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.Schulz Jul 12 '13 at 11:29
3
$\begingroup$

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.

$\endgroup$

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.