Yes, I apologize for the parent comment. I realized I had misread your comment after I had posted and did the edit to try and rectify the situation. I left the

Yes, I apologize for the parent comment. I realized I had misread your comment after I had posted and did the edit to try and rectify the situation. I left the original because I thought it might clarify some of the differences between the machines for people who don't know anything about the subject. I guess I felt that the memory limitation was a misleading way of discussing the machines. Turing machines and PDAs are usually discussed with infinite memory. In practice the input really determines how much memory the machine will use. Furthermore, I believe that the encoding scheme you suggest will use far more space than the equivalent Turing machine or PDA it encodes. Because, for every state in the machine you have to encode every possible memory configuration for that state. That means you have an exponential explosion in the number of states. This gets to the heart of the matter for me: when memory is bounded using the finite version of a PDA will let you match a deeper nesting of parens than a FSM because it will use memory more efficiently. You have to put the states of the machine somewhere and that place is either memory or hardware which are both limited.