1) Determine CFG with no useless symbols equivalent to : S→AB | CA , B→BC | AB, A→a , C→aB | b.
2) create CFG without Ε production from : S →a | Ab | aBa , A →b | Ε , B →b | A.
3) What are the properties of the CFL generated by a CFG?
4) What are the three ways to simplify a context free grammar?
5) What are the closure properties of CFL?
6) Define the pumping lemma for CFLs.
7) Write down the main application of pumping lemma in CFLs?
8) Write down the special features of TM.
9) Describe Turing machine in detail.
10) What do you mean by Instantaneous description of TM?