CNF and GNF for GATE: CFG Simplification and Normal-Form Conversion, Step by Step

Normal-form conversion feels like clerical work until one missed nullable combination changes the language. Questions then build a numerical on that conversion, so a small omission can spoil every later step.

The safe approach is a fixed pipeline whose order is not optional. Epsilon removal comes first, unit removal next, useless-symbol removal after that, and the binary shape rewrite last. Get that order wrong and you redo work you have already finished.

1. Why CNF and GNF exist and what they force

Chomsky Normal Form (CNF) permits productions of the shapes A→BC or A→a, where A,B,C are non-terminals and a is a terminal. If the language contains the empty string, S→ε may be allowed under the standard start-symbol condition.

CNF gives every non-leaf parse-tree node exactly two non-terminal children. That binary shape makes derivation lengths easy to count and supports parsing algorithms.

Greibach Normal Form (GNF) requires A→aα, where the first symbol on the right is a terminal and α is a possibly empty string of non-terminals. Each production introduces exactly one terminal at the front.

That single leading terminal is the point. Every derivation step consumes exactly one input symbol, which is why a GNF grammar maps onto a pushdown automaton mechanically, and why left recursion cannot survive the form.

The contrast is worth memorising:

• CNF controls the complete right-hand-side shape: two non-terminals or one terminal.

• GNF controls the first symbol: one leading terminal, followed only by non-terminals.

2. The simplification pipeline in the right order

Use this sequence before final CNF conversion:

1. Remove epsilon productions.

2. Remove unit productions.

3. Remove useless symbols.

4. Replace terminals in mixed or long right-hand sides, then split long right-hand sides into binary productions.

For epsilon removal, first find every nullable variable. For each production containing nullable occurrences, add every distinct version obtained by retaining or omitting those occurrences. Then delete the epsilon productions, except for the permitted start rule when the language contains epsilon.

A unit production has the form A→B, with one non-terminal on each side. Replace it using the non-unit productions reachable through its unit chain.

A useless symbol is either non-generating, meaning it cannot derive a terminal string, or unreachable from the start symbol. Remove non-generating symbols first and then unreachable symbols.

The order matters. Epsilon removal can create fresh unit productions. Removing unit productions first would force you to repeat that work.

3. Worked example: convert the grammar to CNF

Start with:

S→ASA | aB
A→B | S
B→b | ε

Step 1: remove epsilon productions

B is nullable directly because B→ε. Then A is nullable through A→B. S is not nullable: in S→ASA, removing both A occurrences still leaves S, and S→aB always retains terminal a.

Now expand S→ASA. The two nullable A occurrences can be retained or omitted:

• Retain both: ASA

• Omit the first: SA

• Omit the second: AS

• Omit both: S

The last result is the self-unit rule S→S, which contributes nothing and can be dropped. From S→aB, omitting nullable B adds S→a. After deleting the epsilon rule, we have:

S→ASA | SA | AS | aB | a
A→B | S
B→b

Step 2: remove unit productions

The unit rules are A→B and A→S. Bring the non-unit productions of B and S into A, then delete the unit rules:

S→ASA | SA | AS | aB | a
A→ASA | SA | AS | aB | a | b
B→b

Check the substitution twice. B contributes b. S contributes exactly five non-unit alternatives: ASA, SA, AS, aB, a. Thus A receives six alternatives in total.

Step 3: remove useless symbols

B derives b, so it is generating. A derives a or b, and S derives a, so they are generating too. From S, both A and B appear in reachable productions. No symbol is useless.

Step 4: enforce the CNF shapes

The productions SA and AS already contain exactly two non-terminals. The production ASA has length three, so introduce D1→SA and replace ASA by AD1. The mixed production aB contains a terminal beside a non-terminal, so introduce Ca→a and replace aB by CaB.

The final CNF grammar is:

S→AD1 | SA | AS | CaB | a
A→AD1 | SA | AS | CaB | a | b
B→b
D1→SA
Ca→a

Every alternative now passes a direct audit. AD1, SA, AS, CaB are pairs of non-terminals. The alternatives a and b are single terminals. No unit, epsilon or length-three production remains.

4. Worked example: convert a grammar to GNF

GNF needs no epsilon or unit pipeline of its own, but it does need left recursion gone, because a rule like S→SA can never begin with a terminal. Take this grammar:

S→SA | b
A→a

Remove the left recursion on S first. Writing S→SA | b in the standard epsilon-free form gives:

S→bS1 | b
S1→AS1 | A

Now force a leading terminal on every right-hand side. S→bS1 and S→b already qualify. In S1→AS1 and S1→A, substitute A→a to get S1→aS1 and S1→a. Symbol A is now unreachable, so drop it:

S→bS1 | b
S1→aS1 | a

Both grammars generate b followed by zero or more a symbols, so the language survived the conversion. Count the productions for baa: S→bS1, then S1→aS1, then S1→a. Three rules for a three-symbol string, because each GNF rule contributes exactly one terminal.

5. The two counting formulas GATE builds on

For a non-empty string of length n derived from a CNF grammar, the parse tree has n terminal leaves. A full binary tree with n leaves has n - 1 internal binary nodes.

• Each internal node uses one A→BC production, giving n - 1 applications.

• Each leaf uses one A→a production, giving n applications.

Total production applications are (n - 1) + n = 2n - 1.

For n = 3, this gives 2(3) - 1 = 6 - 1 = 5.

A second check counts the tree directly: three terminal leaves require two binary internal nodes, so 3 + 2 = 5 productions.

In GNF, each production introduces exactly one terminal. A terminal string of length n therefore needs exactly n production applications. For a length-3 string, the GNF count is 3, not 5.

The formulas answer different normal forms. Always confirm the grammar form and the condition n ≥ 1 before using 2n - 1.

6. The traps that cost the whole mark

• From S→ASA, nullable A creates ASA, SA, AS, S. Omitting either SA or AS changes the language.

• Delete an unhelpful self-loop such as S→S. It does not produce terminals or progress a derivation.

• Unit elimination uses the full unit closure, not only one direct substitution.

• Replace a terminal in a mixed right-hand side. A→aB is not CNF even though it has length two.

• A production A→BC is valid CNF but not GNF because it does not begin with a terminal.

• If epsilon belongs to the language and the old start symbol occurs on a right-hand side, introduce a fresh start symbol before conversion.

• Do not apply 2n - 1 to the empty string or to a grammar that is not in CNF.

7. How the exam tests this

Direct questions ask for the nullable variables, the productions left after unit removal, or the number of steps needed to derive a string of length n. Conversion MCQs ask which candidate grammar is truly in CNF or GNF.

For the current syllabus wording and paper pattern, check the official GATE portal of the organising IIT. Use the GATE category to fit normal forms into the wider plan. The explanations in context-free grammars and pushdown automata connect productions with recognition, while the Theory of Computation CFG MCQs turn each conversion step into a testable choice.

Our Theory of Computation practice set carries more than 300 questions on grammars, CFGs and pushdown automata. Convert a fresh grammar from that pool every day for a week and the pipeline stops needing conscious effort.

8. The short version and your next step

Run epsilon, unit and useless-symbol removal in that order. Then replace terminals in mixed productions and split every long right-hand side until each rule is A→BC or A→a. For GNF, remove left recursion first, then substitute until every right-hand side opens with a terminal. In CNF, remember 2n - 1; in GNF, remember n.

Learn the full pipeline in the Theory of Computation course, then solve conversions under time pressure in the GATE Test Series. Your final check is a rule-by-rule shape audit: read every alternative and confirm it is two non-terminals or one terminal, nothing else.