Context Free Grammar

What is Context Free Grammar? & EXAMPLES:

A context-free grammar (CFG) consisting of a finite set of grammar (G) rules is a quadruple (V, T, P, S) where
V is a set of non-terminal symbols.
T is a set of terminal symbols
P is productions; Which are set of Rules;
S is start Symbol.
In a CFG rule must have a Have a L.H.S that is a Single Non-Terminal Have a R.H.S (it is a String of 0 or more terminals & Nonterminals
---------------------------------------------------------------------------------------------------------------
CFG Examples
--------------------------------------------------------------------------------------------------------------
Write a CFG for Balanced Paranetheses Langauge

G={{S,(,)},{(,)},R,S}
V={S,(,)} , T={(,)} S={S} where R=
S ->(S)
S->&#949
S->SS


Write a CFG for aⁿbⁿ
G={{S,a,b},{a,b},R,S}
where R=
S ->aSb
S->&#949


Write a CFG for Even Length Palindrome Where W∈{a,b}^* G={{S,a,b}, {a,b},R,S}
S->aSa
S->bSb
S->&#949

Write a CFG to accept set of all Palindrome over input {0,1} W∈{a,b}^* G={{S,0,1}, {0,1},R,S}
S->0S0
S-> 0
S-> 1
S->1S1
S->&#949

Write a CFG to accept set of odd Palindrome over input {0,1} W∈{a,b}^* 
G={{S,0,1}, {0,1},R,S}

R={
         S->0S0
         S-> 0
         S-> 1
         S->1S1
     }

Write a CFG for Equal no.of a's and b's
S->aSb
S->bSa
S->SS
S->&#949
----------------
OR
 -----------------
S->aSbS
S->bSaS
S-> &#949

Write a CFG for L={n_b(w)=n_a(w)+1}
S->aSb
S->bSa
S->SS
S->b | &#949
Write a CFG for L={n_a(w)=n_b(w)+1}
S->aSb
S->bSa
S->SS
S->a | &#949
Write a CFG for L={0ⁿ1²ⁿ n>=0}
S-> 0S11
S->&#949
Write a CFG for L={0ⁿ1²ⁿ n>=0}
S-> 0S11
S->&#949
Write a CFG for to accept string's of 0's and 1's consists of any no. of 0's &1's.
S->&#949
S-> 0S
S->1S
Write a CFG to accept string consists of even  no. of a's or for language L={a²ⁿ|n>=0}or L={#_amod 2 =0}
S->&#949
S->aaS
Construct a CFG for L={aⁿb^mc^k| m,n>=0 &k=m+n}
Let us rewrite the  L ={aⁿb^mc^k }={aⁿb^mc^m+n }={aⁿb^mc^m cⁿ}=
                                                                              ={aⁿX cⁿ}  where X=b^mc^m

                                                            S-> a S c | X
                                                            X->b X c | &#949

Construct a CFG for L={a^kb^mcⁿ| m,n>=1 & m+n=k}
Let us rewrite the  L ={a^kb^mcⁿ}={a^m+nb^mcⁿ }={a^maⁿb^m cⁿ}={aⁿa^mb^m cⁿ}
                                                                              ={aⁿX cⁿ}  where X=a^mb^m    

                                                            S-> a S c | aaXbc
                                                            X->a X b | &#949
Obtain a CFG for L={aⁿwwRbⁿ| w𝛜{0,1}* n>=2}
                    S-> aaTbb
                    T->aTb|B
                    B->0B0|1B1|&#949

Construct a CFG for L={aⁿbⁿc^m :n,m>=0}
           Let us divide the string into 2 regions: N=aⁿbⁿ   & M=c^m
       
             S-> N M
             N-> aNb |&#949
             M->cM | &#949
Construct a CFG for L={aⁿb^mc^m :n,m>=2}
           Let us divide the string into 2 regions: N=aⁿ  & M=b^mc^m
       
             S-> N M
             N-> aN | aa
             M->bMc | bbcc       
Construct a CFG for L={a^mbⁿc^m :n,m>=0}
S-> aSc | T
T-> bT | &#949