4 ms·
The informal answer is that you can treat two stacks like one tape. The top of the first stack is the current location on the tape. You can move the tape head
by Adrock 13y ago
The informal answer is that you can treat two stacks like one tape. The top of the first stack is the current location on the tape. You can move the tape head to the left by popping from Stack 1 and pushing that value onto Stack 2. Pop from Stack 2 and push on Stack 1 to move to the right.
What's really funky is that a DFA with a queue is a Turing machine. You can show this by putting a sentinel value in the queue that separates two stacks and having some crazy loop structures that allow you to push and pop from the two stacks it represents.
- chas 13y agoAnother way of saying this is that the two stacks as a list zipper[1], which makes the correspondence between a DFA with arbitrarily writable memory and a DFA with two stacks readily apparent. [1]http://en.wikipedia.org/wiki/Zipper_(data_structure)#Example:_Bidirectional_list_traversal http://en.wikipedia.org/wiki/Zipper_(data_structure)#Example...