TOC | Unit 3 | Context Free Grammar and Context Free Language | SPPU T.E. Comp & I.T. | ONESHOT

For Hard Copy Books & Notes

Website Link (for PC/Laptop users): https://classplusapp.com/w/haris-chau...

App Link (Android): https://play.google.com/store/apps/de...

App Link (iOS): https://ijneis.courses.store/

WhatsApp: +91 968 960 2477
Instagram:   / harischaus  
LinkedIn:   / haris-chaus-721734208  

Theory of Computation

Computer Engineering Syllabus:

Unit 3 - Context Free Grammar (CFG) and Context Free Language (CFL)

Basic Elements of Grammar, Formal Definition of Context Free Grammar, Sentential form,
Derivation and Derivation Tree/ Parse Tree, Context Free Language (CFL), Ambiguous Grammar,
writing grammar for language. Simplification of CFG: Eliminating Є-productions, unit productions,
useless production, useless symbols. Normal Forms: Chomsky Normal Form, Greibach Normal
Form, Pumping Lemma for CFG, Closure properties of CFL, Decision properties of CFL, Chomsky
Hierarchy, Cock-Younger-Kasami Algorithm.

Information Technology Syllabus:

Unit -3: CONTEXT FREE GRAMMAR AND LANGUAGE

Grammar: Introduction and representation, Chomsky Hierarchy, Formal definition of Regular
Grammar(RG), Conversions: LRG to RLG, RLG to LRG, RG to FA, FA to RG.
Context Free Grammar (CFG): Definition of CFG, Derivation tree, sentential forms, Leftmost and
Rightmost derivations, Ambiguous Grammar and unambiguous grammar, Context Free Language
(CFL).
Grammar Simplification, Normal forms: Chomsky Normal Form, Greibach Normal Form. Closure
properties of CFL, Pumping lemma for CFL

TOC Oneshot
Context Free Grammar (CFG) and Context Free Language (CFL) Oneshot

Theory of Computation for Endsem
SPPU Endsem Exam
TE Endsem Exam
Computer Engineering
Artificial Intelligence and Data Science
Information Technology