I tried to solve this exercise:

Discuss the normal forms (CNF or GNF) of a grammar with productions:

$S\rightarrow BC | CB$

$B\rightarrow cB | c$

$C\rightarrow cC | \epsilon$

Same request with the following grammar:

$S\rightarrow BC | CB$

$B\rightarrow cB | c$

$C\rightarrow cC | c$

I applied the rules to convert a grammar into its normal form and I think that both are CNFs.

For the first grammar:

$S\rightarrow BC | CB|C'B|c$

$B\rightarrow C'B | c$

$C\rightarrow C'C | c$

$C'\rightarrow c$

For the second grammar:

$S\rightarrow BC | CB|TB|c$

$B\rightarrow TB | c$

$C\rightarrow TC | c$

$T\rightarrow c$

Is that correct?

  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Aug 11 '17 at 12:12
  • $\begingroup$ @Raphael I don't think that was the question. The question was "I converted to normal form and got CNF, so why are they mentioning GNF?" $\endgroup$ – Yuval Filmus Aug 11 '17 at 12:54
  • $\begingroup$ @YuvalFilmus Exactly! $\endgroup$ – PCNF Aug 11 '17 at 12:55
  • 1
    $\begingroup$ @YuvalFilmus It's hard to say, the post is very thin. The only question in the body is, "Is that correct?" $\endgroup$ – Raphael Aug 11 '17 at 12:55

A context-free grammar is in Chomsky normal form if all productions are of the form $A \to BC$ (where $B,C$ are not the starting symbol), $A \to a$, or $S \to \epsilon$, where $S$ is the starting symbol. A context-free grammar is in Greibach normal form if all productions are of the form $A \to a\alpha$, where $\alpha$ consists only of non-terminals (but not the starting symbol), or $S \to \epsilon$, where $S$ is the starting symbol.

Every context-free grammar has an equivalent context-free grammar in Chomsky normal form, and another one in Greibach normal form; there could be several equivalent context-free grammars in either normal form.

When you applied the rules to convert your grammars into normal form, you got Chomsky normal form because the rules were designed for converting a given context-free grammar to Chomsky normal form. You could follow other rules and get Greibach normal form.

  • $\begingroup$ So I guess that what I've written is correct but I can convert the two grammars also into GNF, right? $\endgroup$ – PCNF Aug 11 '17 at 11:52
  • $\begingroup$ Yes, for every context-free grammar there exists an equivalent grammar in GNF. $\endgroup$ – Yuval Filmus Aug 11 '17 at 12:35
  • $\begingroup$ thank you. But I have one last doubt. If a CFG can be converted in CNF and also in GNF what is the aim of this exercise? $\endgroup$ – PCNF Aug 11 '17 at 12:48
  • 1
    $\begingroup$ The exercise wants you to practice the algorithms for converting a CFG to CNF and to GNF. Perhaps a better question is why we care about CNF and GNF. CNF is used in many places, for example in the CYK algorithm, in the pumping lemma, and elsewhere. GNF is used for converting a context-free grammar to a pushdown automaton. $\endgroup$ – Yuval Filmus Aug 11 '17 at 12:51

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.