1,234 views

1 Answer

1 votes
1 votes
DFSM + 1 stack = DPDA

NFSM + 1 stack = NPDA

and we know  power(NPDA)>power(DPDA)

DFSM + 2 stack = DTM

NFSM + 2 stack = NTM

and power(DTM) = power(NTM)

even adding more stack to TM does not improve expressing power.  ie. I can say a FSM with n stack is same powerful than a FSM with 2 stack.
edited by

Related questions

0 votes
0 votes
0 answers
1
Naveen Kumar 3 asked Nov 8, 2018
660 views
Answer the following:-1. Worst case time complexity to minimize DFA?2. Best case time complexity to minimize DFA?3. Worst case time complexity to minimize NFA?4. Best cas...
1 votes
1 votes
0 answers
2
ankitgupta.1729 asked Feb 25, 2018
568 views
Is minimization of Finite State Machine(FSM) based on Dynamic Programming(DP) paradigm ? If yes , then what should be the optimal substructure and overlapping subproblems...
0 votes
0 votes
0 answers
3
nitish asked May 4, 2017
383 views
0 votes
0 votes
0 answers
4
thor asked Nov 14, 2016
186 views
Please explain