Q.No.1. In CFG, sometimes all the production rules and symbols are not needed for the derivation of strings. Beside this, there may also be some NULL Productions and UNIT Productions. Elimination of these productions and symbols is called simplification of CFG. Simplification consists of the following steps.

• Reduction of CFG.
• Removal of Unit Productions.
• Removal of NULL Productions.

So Simplify the Given CFG

S bS | aA | dD | aF

A bA | aF | a |

F bF | b |

Q.No.2. Make a CFG for the language having EVEN number of as and EVEN number of bs and starts with ab and ends on ba defined over ={a,b}.

Q.No.3. Construct Pushdown Automata (PDA) for the language {a²ⁿbⁿ²} for n=2,3,4, defined over ={a,b}.

Q.No.4. Describe the language of the given CFG

SSS | BS | SB | USU |

Baa | bb

Uba | ab

Also check whether the given CFG is Ambiguous or not?