Redirected
recategorized by
2,361 views

6 Answers

1 votes
1 votes
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

Related questions

0 votes
0 votes
3 answers
1
Pooja Khatri asked Jul 13, 2018
3,222 views
Pushdown automata can recognize language generated by _______Only context free grammarOnly regular grammarContext free grammar or regular grammarOnly context sensitive gr...
1 votes
1 votes
2 answers
2
Pooja Khatri asked Jul 13, 2018
15,274 views
Two finite state machines are said to be equivalent if they:Have the same number of edgesHave the same number of statesRecognize the same set of tokensHave the same numbe...
0 votes
0 votes
2 answers
3
0 votes
0 votes
1 answer
4
Pooja Khatri asked Jul 13, 2018
1,238 views
To obtain a string of n Terminals from a given Chomsky normal from grammar, the number of productions to be used is$2n-1$$2n$$n+1$$n^2$