CFL in TOC

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= {aⁿbⁿ 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 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.