PPT: Properties of Context-Free Languages Notes | EduRev

Theory of Computation

Computer Science Engineering (CSE) : PPT: Properties of Context-Free Languages Notes | EduRev

 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 cleanup
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

Important questions

,

Semester Notes

,

Viva Questions

,

practice quizzes

,

Previous Year Questions with Solutions

,

pdf

,

mock tests for examination

,

shortcuts and tricks

,

video lectures

,

PPT: Properties of Context-Free Languages Notes | EduRev

,

Extra Questions

,

Sample Paper

,

ppt

,

PPT: Properties of Context-Free Languages Notes | EduRev

,

Objective type Questions

,

study material

,

MCQs

,

Exam

,

Summary

,

past year papers

,

PPT: Properties of Context-Free Languages Notes | EduRev

,

Free

;