Theory of Automata

Context Free Language



Context free grammar has production rules which are used to generate context free language. Context free languages are accepted by Push down automata (PDA).

  • All Regular languages and CFL are accepted by PDA.
  • 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)

where

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

Example Of Context Free Language

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



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

Above production rules generates the strings having equal number of a’s and b’s. it is an example of context free language

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest