The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
677 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 (495 points) | 677 views

4 Answers

+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 Boss (25.6k points)
+1 vote
  • PDA + 1 AUXILIARY IS EQUVALENT TO TURING MACHINE

answered by Boss (23.3k points)
0 votes
PDA already has 1 stack , so it requires one more stack. Therefore answer C
answered by (327 points)


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

39,439 questions
46,622 answers
139,360 comments
57,009 users