Marks CO (01) CO2 3. Assume suitable data wherever necessary. Question Description of Question 1 Choose the correct option from the following. (a) Regarding the power of recognition of languages, which of the following statements is false? I. The non-deterministic finite state automata are equivalent to deterministic finite-state automata. II. Non-deterministic Push down automata is equivalent to deterministic Push down automata. III. Non-deterministic Turing machines are equivalent to deterministic Turing machine. IV. Multi-tape Turing machine are equivalent to Single-tape turing machine. b) Which of following statement is true about given grammar G S-> aS aSbs (01) CO2 c) (01) CO1 I. Set of all strings having more a's than b's. II. Set of all strings of the form arbn, n>=0 III. Set of all strings where each prefix contains at least as many a's as b's. IV. None of the above Consider the two statements. I. It is possible to construct a NFA with more number of states than its equivalent minimum DFA. II. There can be a DFA with more than one start state. Choose the correct option. A. Both are false B. Only I is false C. Only II is false D. Both are true Which of the following statements is incorrect? I. b*ab*ab* referes to the set of all strings that contain exactly two a's over an alphabet {a,b} II. The problem of equivalence of two DFA's is decidable. III. (c*(ab*)*+d)* contains abcd. IV. None of the above d) ( 01) CO2