1. Draw Chomsky Hierarchy with grammar, language and automata used.
2. Give description of automata theory.
3. Prove by Mathematical induction 1 + 3 + 5 + 7 + ... + 2n-1 = n2
4. Determine string acceptability of 01100 using transition function for below automata. Draw Transition table.
5. Define alphabet, string, language, grammar. Define Pigeon hole principle.
Section B
(Long Answer Type) 2 questions of 20 marks each (any 1)20
1. Prove by Mathematical induction 12+22+32+42+………+n2 = n(n+1)(2n+1)/6
2. Construct a DFA equivalent to the NFA given below:
