CNF (Chomsky Normal Form)
Definition:
CNF is a restricted form of Context-Free Grammar (CFG) where every
production must be either:
A→BCA→BC, with BB and CC as non-terminals
A→aA→a, with 'a' as a terminal
S→εS→ε, allowed only for the start symbol
Key Properties:
No production can have more than two non-terminals on the right-hand side.
No mixing of terminals and non-terminals except the terminal-only rule.
Null (ε) productions and unit productions are removed before conversion
except for the start symbol.
Applications:
Useful for bottom-up parsing algorithms like CYK.
Makes grammar suitable for binary tree parsing.
GNF (Greibach Normal Form)
Definition:
GNF is a CFG form where every production rule starts with a terminal,
followed optionally by non-terminals:
A→aαA→aα, where 'a' is a terminal, αα is a sequence of non-terminals
(possibly empty).
Key Properties:
No production may start with a non-terminal.
No epsilon (ε) rules except possibly for the start symbol if language includes
ε.
Eliminates left recursion during conversion.
Applications:
Best suited for top-down parsing, e.g., recursive descent.
Allows direct derivation from the input string’s first symbol, aiding
sequential parsing approaches.
Comparison Table
Feature CNF GNF
Right-hand form Two non-terminals or a terminal Terminal followed by non-terminals
Feature CNF GNF
Parsing use Bottom-up (CYK) Top-down (recursive descent)
ε (Null) allowed? Only for start symbol Only for start symbol
Conversion Standard steps, moderate effort More complex, left recursion must go
Example Rule A→BC,A→aA→BC,A→a A→a X YA→aXY
Additional Points
Both CNF and GNF allow conversion from any context-free grammar, but
GNF conversion is more complicated due to left recursion removal.
In CNF, derivations facilitate binary splitting of strings, great for bottom-up
algorithms.
In GNF, rules facilitate immediate terminal match, simplifying predictive top-
down parsing.
Chomsky Normal Form (CNF)
A CFG is in Chomsky Normal Form if every production is of the form:
1. A→BCA \to BCA→BC (where B,CB, CB,C are non-terminals, not start symbol)
2. A→aA \to aA→a (where aaa is a terminal)
3. S→ϵS \to \epsilonS→ϵ (allowed only if language contains ε)
✦ Steps to Convert CFG to CNF:
1. Remove null (ε) productions (except for start symbol if needed).
2. Remove unit productions (rules like A→BA \to BA→B).
3. Remove useless symbols (non-terminals that never produce terminals).
4. Convert longer productions into binary form, e.g.,
A→BCD⇒A→BX, X→CDA \to BCD \quad \Rightarrow \quad A \to BX, \; X \to
CDA→BCD⇒A→BX,X→CD
Example:
Grammar: S→AB∣aS \to AB | aS→AB∣a , A→aA \to aA→a, B→bB \to bB→b
Already in CNF because productions are of type A→aA \to aA→a and S→ABS \to ABS→AB.
3. Greibach Normal Form (GNF)
A CFG is in Greibach Normal Form if every production is of the form:
A→aB1B2...Bk(k≥0)A \to aB_1B_2...B_k \quad (k \geq 0)A→aB1B2...Bk(k≥0)
That means the right-hand side begins with a terminal, followed by zero or more non-
terminals.
Example:
A→aBCA \to aBCA→aBC ✅ (allowed)
A→bA \to bA→b ✅ (allowed, since k=0k=0k=0)
A→BAA \to BAA→BA ❌ (not allowed, starts with non-terminal)
4. Comparison of CNF vs GNF
Feature CNF GNF
Rule forms A→BCA \to BCA→BC, A→aA \to aA→a A→aB1B2...BkA \to aB_1B_2...B_kA→aB1B2...Bk
ε-production Allowed only for start symbol Not allowed
Parsing use CYK Algorithm (bottom-up parsing) Top-down parsing
Structure Binary split of non-terminals Every rule starts with terminal
5. Why Important?
CNF: Useful for CYK parsing algorithm (membership test in O(n³)).
GNF: Useful for top-down parsing, ensures no left recursion.
Both forms are used to prove properties of CFLs and simplify parsing.
✅ Key Exam Points:
CNF: Rules are either A→BCA \to BCA→BC or A→aA \to aA→a.
GNF: Rules start with a terminal: A→a...A \to a...A→a....
CNF → bottom-up parsing (CYK).
GNF → top-down parsing.
