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) 0
(2) 1
(3) 1 or more
(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
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.