# Chomsky or Greibach Normal Form?

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?

• 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. – Raphael Aug 11 '17 at 12:12
• @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?" – Yuval Filmus Aug 11 '17 at 12:54
• @YuvalFilmus Exactly! – PCNF Aug 11 '17 at 12:55
• @YuvalFilmus It's hard to say, the post is very thin. The only question in the body is, "Is that correct?" – 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.