UGC NET Computer Science July 2018 - II Question 33

Question 33

---

33. A pushdown automata behaves like a Turing machine when the number of auxiliary memory is :

Options:

1. (1) 0
2. (2) 1
3. (3) 1 or more
4. (4) 2 or more

Answer : (4) 2 or more

Explanation Question 33

PDA have only one stack...
with 2 stacks we can implement queue → T(n+2) is sufficient to form Turing Machine.
moreover expressive power of T(n+2) = T(n+3) = T(n+4) etc..
Therefore we need one more extra auxiliary stack memory for PDA or we need atleast 2 auxiliary memory to implement TM

So, Option (4) is correct answer.

Previous	Next
UGC NET CS 2018 July - II Question 32	UGC NET CS 2018 July - II Question 34