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

Описание: App Link for Notes: https://play.google.com/store/apps/de...

Webpage Link (for PC/Laptop users) for Notes: https://web.classplusapp.com/login?or...

The notes are available in an online format and can be accessed via the app or the website (for laptop/PC). For content protection, downloading or printing is not allowed.

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