Context-free grammar has production rules that are used to generate cfl (context-free language) in toc. Context-free languages are accepted by push-down automata (PDA).

  • PDA accepts all Regular languages and CFL.
  • For all context-free languages, there must be one comparison in terminals of string e L= {anbn n>=0}

A context-free Grammar (CFG) is a 4-tuple such that

G = (V , T , P , S)


  • V = Finite set of variables / non-terminal symbols. These are denoted by capital letters.
  • T = Finite set of terminal symbols. These are used to replace the variables. These are denoted by lowercase letters.
  • P = Production rules are used to generate CFL. i.e. A → α , where A ∈ V and α ∈ (V ∪ T)*. Remember that the left side must contain only one variable, but the right side ((V ∪ T)*) may contain more than one terminal and non-terminal.
  • S = Start symbol

Example Of CFL in TOC

Consider a grammar G = (V, T, P, S) where-

  • V = { S }
  • T = { a , b }
  • P = { S → aSbS , S → bSaS , S → ∈ }
  • S = { S }

The above production rules generate the strings having an equal number of a’s and b’s. It is an example of context-free language.