IT503(A) Unit 3
Theory of Computation

Context Free Grammar

Unit 3 Study Material

Download detailed notes, important questions and PYQ analysis for IT503(A) Theory of Computation Unit 3.

🌳 CFG

Context Free Grammar is used to generate context-free languages.

🧩 Parse Tree

Parse tree represents the derivation structure of a grammar.

📐 CNF / GNF

Normal forms simplify CFGs for parsing and language analysis.

📘

Detailed Notes

Complete notes on context-free grammar, derivation trees, ambiguity, simplification of CFG, Chomsky Normal Form, Greibach Normal Form, pumping lemma for CFL and closure properties.

Download PDF
⭐

Important Questions

Important RGPV questions on CFG design, parse trees, ambiguity removal, CNF conversion, GNF conversion, pumping lemma for CFL and closure properties of CFL.

View Questions
📄

PYQ Analysis

Previous year questions and repeated topics from Theory of Computation Unit 3 for quick exam revision.

Open Analysis

Unit 3 Topics

Context Free Grammar
Introduction to CFG
Derivation Trees
Parse Trees
Leftmost Derivation
Rightmost Derivation
Ambiguity in Grammar
Ambiguous Grammar
Simplification of CFG
Removal of Null Productions
Removal of Unit Productions
Removal of Useless Symbols
Normal Forms of CFG
Chomsky Normal Form
Greibach Normal Form
Pumping Lemma for CFL
Applications of Pumping Lemma
Decision Algorithms for CFG
Designing CFGs
Closure Properties of CFL
CFL Union Closure
CFL Concatenation Closure
CFL Kleene Closure