The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
1.2k views
A pushdown automata behave like a Turing machine when number of auxiliary memory is:

(1)  0       

(2)  1

(3)  1 or more

(4) 2 or more
asked in Theory of Computation by Active (1.7k points) | 1.2k views

4 Answers

+2 votes
  • PDA + 1 AUXILIARY IS EQUVALENT TO TURING MACHINE

answered by Boss (25.3k points)
+1 vote
option 4
answered by (75 points)
+1 vote
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

Option D is correct
answered by Veteran (55.7k points)
0 votes
PDA already has 1 stack , so it requires one more stack. Therefore answer C
answered by (449 points)

Related questions

0 votes
1 answer
1
asked Jul 11, 2018 in Theory of Computation by Sanjay Sharma Veteran (50.5k points) | 151 views
+1 vote
1 answer
4
asked Dec 31, 2018 in Programming by vcrname9295 (95 points) | 50 views
0 votes
0 answers
5
asked Dec 30, 2018 in Operating System by xdilwar (455 points) | 53 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,894 questions
52,261 answers
182,169 comments
67,679 users