CFG Normal Forms (CNF & GNF)
Context-Free Grammar Normal Forms
Learn to convert CFGs to Chomsky Normal Form (CNF) and Greibach Normal Form (GNF)
Theory & Concepts
Definition:
Normal forms are standardized representations of CFGs that simplify parsing and theoretical analysis.
Key Points:
- CNF: All productions are A → BC or A → a (binary or terminal)
- GNF: All productions are A → aα (start with terminal)
- Both forms are equivalent to the original grammar in language generation
- CNF is useful for CYK parsing algorithm
- GNF enables top-down parsing without backtracking
Applications:
- Parser construction and optimization
- Complexity analysis of CFGs
- Formal language theory proofs
- Compiler design and implementation
University Guidelines
Exam Weightage
10-15 marks MarksSyllabus Coverage:
- CNF Conversion
- GNF Conversion
- Normal Forms
- CFG Simplification
Common Questions:
- Convert given CFG to Chomsky Normal Form
- Convert given CFG to Greibach Normal Form
- Explain the steps in normal form conversion
- Compare CNF and GNF representations
Exam Tips:
Follow systematic steps: remove ε-productions, unit productions, then convert
Be careful with variable renaming in CNF
GNF conversion is complex - focus on understanding the concept
Practice with simple grammars first
Algorithm Details
O(n³) for CNF, exponential for GNF in worst case
Time Complexity
O(n²) for storing intermediate productions
Space Complexity
Algorithm Steps:
- 1CNF Conversion:
- 21. Remove ε-productions (except for start symbol if needed)
- 32. Remove unit productions (A → B)
- 43. Replace terminals in long productions with new variables
- 54. Break productions longer than 2 symbols into binary productions
- 6
- 7GNF Conversion:
- 81. Convert to CNF first
- 92. Eliminate left recursion
- 103. Ensure all productions start with terminals
Input CFG
CNF Conversion Steps
Click "Convert to CNF" to see the conversion process.
CFG Normal Form Conversion Result
Input: "CFG with 7 productions"
REJECTED
CNF conversion not completed
Simulation Steps
Step-by-step execution trace