Q16. Given the following statements :

(i) The power of deterministic finite state machine and non-deterministic finite state machine are same.
(ii) The power of deterministic pushdown automaton and non-deterministic pushdown automaton are same.
Which of the above is the correct statement(s) ?
(A) Both (i) and (ii)
(B) Only (i)
(C) Only (ii)
(D) Neither (i) nor (ii)
Answer(B) Power of deterministic finite state machine and non-deterministic finite state machine are same.
Explanation.
Theorem:
For each non-deterministic finite state machine N, we can construct a deterministic finite state machine D such that N and D accept the same language.
Theorem: Every deterministic finite state machine can be regarded as a non–deterministic finite state machine that just doesn’t use the extra non–deterministic capabilities. a pushdown automaton (PDA) is a type of automaton that employs a stack.Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines. Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages. Mainly the former are used in parser design