Practic Mode : Paper-II & III On Topic : Theory of Computation

Que : 1 . Given the following statements :
i) The power of deterministic finite state machine and nondeterministic finite state machine are same.
ii) The power of deterministic pushdown automaton and nondeterministic pushdown automaton are same. Which of the above is the correct statement(s) ? (J-2012)

1. Both (i) and (ii)
2. Only (i)
3. Only (ii)
4. Neither (i) nor (ii)
Please Select Ans Options .

Option 2 is Correct Answer.
Finite machine is of two types. One is deterministic finite state machine and the other one non deterministic finite state machine.
Both these machine accept regular language only.
So the power of DFA = NFA. So the first statement is true.
2. Pushdown automaton and the power of deterministic and non-deterministic being the same.
PDA has more power than FA because PDA has a memory and so can accept large class of languages than FA.
PDA accepts the language of context free grammar.
The power of DPDA is less than NPDA because NPDA accepts a larger class of context free language.
Turing machines can accept a more large class of language.
Therefore it is the most powerful computational model. The power of deterministic and non deterministic turing machine is the same.