Re:What is the enlightenment I'm supposed to attain after st...
by chas on Sunday November 24, 2013 @06:01PM
(#6791576)
Another 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...
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.