# 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
^{n}b^{n}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.