Theory of computation subjective question for competitive exam

Q1.Difference b/w dfa and nfa

DFA                                                               NFA                                       
1.Each transition leads to exactly one state.                    1.A transition leads to a subset of states.
2.Accept input if last state is final state.                     2. Accept input if one of the last state is final state.
3.Backtracking is allowed in dfa.                                3.Backtracking not possible.   
4.Require more space.                                            4.Require less space.
5.Empty string transition not allowed in dfa.                    5.Permits empty string transition.
6.Q*input->Q                                                     6.Q*input->2powerQ                                               

Q2.Diff b/w type0 and type1 grammar

Type0                                              Type1
1. Recursively enumerable language.               1.Context sensitive language.
2.Use turing machine.                             2.Linear bounded automata. 
3.No restriction in production rule.              3. αAβ->αyβ

Q3.Why finite state machine cannot recognise a palindrome

Finite state machine have little memory to keeep track of last input.
Palindrome problem requires two basic constraint
1.Find the midpoint.
2.Match with the subsequent previous input.
Finite state machine cannot do either of them.

Q4.Diff b/w dpda and npda

DPDA                                                                                            NDPDA
1.It is less powerful than npda.                                                             1.It is more powerful than npda. 
2.In DPDA from each state on input symbol there is exactly one transition.                   2.In NDPDA from each state on input symbol there is zero or more than one transition.   
3.Q*Σ*Γ->Q*Γ                                                                                 3.Q*(Σ*NULL)*Γ->Q*Γ
4.In dpda cannot be null transition.                                                         4.In dpda can be null transition.  
5.Implementation of dpda with computer program is simple.                                    5.Implementation of Ndpda with computer program is difficult.

Q5.Describe chomsky classification

Noam chomsky gave mathematical model of grammar which is effective for writing computer language.
Type0                                Type1                            Type2                       Type1
Unrestrictrd grammar                 Context sensitive grammar         Context free grammar.      Regular grammar
Recursive enumberable language.      Context sensitive language        Context free language.     Regular language.     
Turing machine                        Linear bounded automata.         Push down automata         Finite automata.