You have to imagine the epsilon state transition as a sort of fun water slide that your nonterminals can go down and put their little arms up in the air like wheeeee. This immediately elucidates why nondeterministic finite state automata, and especially nondeterministic pushdown automatas, are so much more nicer than their deterministic counterparts (especially in the case of PDAs where the fun water slide can push you onto the stack and pull you back out of it, which is way more fun and therefore more expressive)
Post
Replies:
7
@dragon i'm so deliriously enchanted with PDAs............we have been in the honeymoon period for several years now
@hipsterelectron theyre really beautiful but im kinda mad at them for NPDAs and DPDAs not being computationally equivalent. NFAs and DFAs are, and so are NTMs and DTMs, so why not PDAs!!!! whats up with that!!!!!
@dragon two PDAs are equivalent to a turing machine still curb stomps my tiny brain
@dragon jeremy spinrad mentioned with a mischievous grin that it's kinda like two sides of a turing tape together and that is almost a valid proof but not quite
@dragon it is not the least powerful equivalent to a turing machine i'm p sure you can add something smaller to a single stack but two independent stacks is generally equivalent to a turing machine and this is actually pretty useful
@hipsterelectron @dragon D@nny, have you ever tried learning Forth?
