Context-free grammar, in short CFG, is type 2 grammar according to the Chomsky hierarchy. The language generated by the CFG is called context-free language (CFL). In the previous chapters, we have discussed about finite automata and regular expression which are related to regular grammar. Regular grammar is a subset of CFG. In this chapter, we shall learn about CFG, how to derive a language from a CFG, simplification of CFG, transformation of CFG into normal form, and the pumping lemma for CFG.
According to the Chomsky hierarchy, context-free grammar, or in short CFG, is type 2 grammar.
In mathematical description, we can describe it as
Where all the production are in ...