Page 1 1 Properties of Context-free Languages Page 2 1 Properties of Context-free Languages 2 Topics 1) Simplifying CFGs, Normal forms 2) Pumping lemma for CFLs 3) Closure and decision properties of CFLs Page 3 1 Properties of Context-free Languages 2 Topics 1) Simplifying CFGs, Normal forms 2) Pumping lemma for CFLs 3) Closure and decision properties of CFLs 3 How to “simplify” CFGs? Page 4 1 Properties of Context-free Languages 2 Topics 1) Simplifying CFGs, Normal forms 2) Pumping lemma for CFLs 3) Closure and decision properties of CFLs 3 How to “simplify” CFGs? 4 Three ways to simplify/clean a CFG (clean) 1. Eliminate useless symbols (simplify) 2. Eliminate e-productions 3. Eliminate unit productions A => e A => B Page 5 1 Properties of Context-free Languages 2 Topics 1) Simplifying CFGs, Normal forms 2) Pumping lemma for CFLs 3) Closure and decision properties of CFLs 3 How to “simplify” CFGs? 4 Three ways to simplify/clean a CFG (clean) 1. Eliminate useless symbols (simplify) 2. Eliminate e-productions 3. Eliminate unit productions A => e A => B 5 Eliminating useless symbols Grammar cleanupRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

18 videos|43 docs|39 tests