UNIT IV - Context-Free Grammars
UNIT – IV- Mathematical Foundations of Computer Science & Automata Context-Free Grammars Syllabus: Context-Free Grammar (CFG) · Derivations and Parse Trees · Ambiguity · CFG Simplification · Chomsky Normal Form (CNF) · Greibach Normal Form (GNF) · Pumping Lemma for CFLs 1.1 Introduction A Context-Free Grammar (CFG) is a formal grammar used to describe the syntax and structure of languages. It is widely used in compiler design, programming languages, and the study of formal languages. A CFG specifies how strings can be generated using a set of production rules. Why “context-free”? A non-terminal can be replaced according to a production rule regardless of the symbols surrounding it (its context). 1.2 Formal Definition A CFG is a four-tuple: G = (V, T, P, S) Component Meaning Example V Finite set of variables / non-terminal symbols ...