# Converting context-free grammar to chomsky normal form

I'm trying to prove that the following CFG can be converted to a CNF:

S -> aAB
A -> aAa
A -> bb
B -> a


Here below is how I've managed so far:

### Step 1: add a new start state

S0 -> S
S -> aAB
A -> aAa
A -> bb
B -> a


### Step 2: remove epsilon rules

There are no such rules in this CFG.

### Step 3: remove non-terminal to non-terminal rules

S0 -> aAB
S -> aAB
A -> aAa
A -> bb
B -> a

Step 4: make right-hand-side not contain more than $2$ non-terminals or $1$ terminal:
S0 -> BC
S -> BC
A -> BF | EE (A -> aAa and A -> bb in one line)
B -> a
C -> AB
E -> b
F -> AB


So this is where I got confused. I have now both C and F that go to AB. If I've done this correctly that would mean that either C or F can simply be removed. Or, of course, I've done something wrong in this procedure.

• "I'm trying to prove that the following CFG can be converted to a CNF:" -- Every CFG can; it's called Chomsky Normal Form for a reason. Just follow the algorithm from that proof. Sep 19, 2016 at 19:43

## 4 Answers

You're right to be cautious, but there is nothing wrong.

A → BC,  or
A → a,   or
S → ε,   where S is the start symbol.


Consider the grammar

S → TU
S → UT
T → a
U → a


Is this a valid context-free grammar in Chomsky Normal Form?

Yes, it is. Each rule is of one of the allowed forms.

But - you say - T and U have the exact same rules; one can be replaced with the other!

Congratulations: you have invented a normal form! A grammar is in Byfjunarn Normal Form if and only if it has no two different nonterminals for which the rules have the exact same right hand sides.

This is clearly a normal form: in fact, normalizing grammars into this form is so easy that we do it routinely, without even thinking about it.

But the algorithm you're using to bring arbitrary grammars into Chomsky Normal Form doesn't. Why should it? Grammars can be in Chomsky Normal Form without being in Byfjunarn Normal Form; the example proves it. Yes, it would be easy to modify the algorithm to bring grammars not only into Chomsky Normal Form, but also into Byfjunarn Normal Form. But nobody asked it to. Except you.

Just let the poor algorithm go about its ways. You know what to do once it's finished :-)

• Thank you for the answer. Was both fun to read and very informatic. I cannot upvote it yet but i will as soon as i get enough points. Cheers! Sep 20, 2016 at 9:08

Here is Swaira Shabbir's image answer, converted into mathjax:

\begin{align} S&\rightarrow aAB\\ A&\rightarrow aAa\\ A&\rightarrow bb\\ B&\rightarrow a\\ \end{align} CFG-to-CNF
$$\underline{Step\text{ }1}$$: Not hold, as there is no 'S' on right side of any production.
$$\underline{Step\text{ }2}$$: No Epsilon rules here i.e. No Useless, Null & Unit Productions.
$$\underline{Step\text{ }3}$$: Non terminal -> 2 Non terminals
Non Terminal -> one terminal
Production that does not follow these rules, convert their right side to uppercase & add new productions. \begin{align} X&\rightarrow a\\ Y&\rightarrow b\\ S&\rightarrow XAB\\ A&\rightarrow XAX\mid YY\\ B&\rightarrow a\\ \end{align} $$\underline{Step\text{ }4}$$: Reduce length of right side of productions to '2' terminals by introducing new productions. \begin{align} X&\rightarrow a\\ Y&\rightarrow b\\ R&\rightarrow XA\\ S&\rightarrow RB\\ A&\rightarrow RX\mid YY\\ B&\rightarrow a\\ \end{align} So required CNF Form is:

• You don't need to show us the Mathjax source; we can click 'edit' and see it. The answer seems to be missing something at the end, since it doesn't appear to tell us what the final CNF form is.
– D.W.
Mar 21, 2020 at 16:15

1) no empty production 2) no unit production 3) convert all mix term and terminal greater than one into capital

S->AAB A->AAB/BB B->a A->a

4) Reduce the length of each non terminal upto 2 and add new rule S->TB A->TB/BB B->a A->a T->AA (new rule)

• I don't see how this answers the question. A little explanation would make this answer much clearer. In particular, what does this answer add to the existing answer above? Feb 11, 2019 at 9:25

Rules for conversion of CFG to CNF https://www.geeksforgeeks.org/converting-context-free-grammar-chomsky-normal-form/

Here is the solution of question:

• Please see this MathJax tutorial so that you can write your answer instead of posting a picture of a handwritten solution. Also, try to make your solutions stand alone and not require links to external sources for them to be understood. Feb 21, 2020 at 16:51