3 added 109 characters in body edited Oct 24 '18 at 14:01 Raphael♦ 59k2626 gold badges144144 silver badges327327 bronze badges There are several possible layers to your question. Why must PDAs have a stack? -- By definition! That's just how it is. But why are they defined like that? -- Somebody thought it might turn out interesting. And apparently it did, because many people (read: the entire field) has agreed to use that definition. Why is it interesting? -- See reinierpost's answer. Why does my teacher choose to teach PDAs? -- That's a multi-facetted issue; see here for a similar question. The answers carry over. I'd like to expand on the second bullet a little. How do different definitions come about? If you take finite control with different memory models, the resulting classes of automata have very different capabilities. In fact, that's a huge part of what automata theory concerns itself with. Once you realize that playing around with definitions can lead to interesting concepts, it's only natural for researchers -- a curious bunch! -- to try and explore the space of possible models. To list just a few examples of ideas people have had: finite memory --> regular single stack --> context-free single queue --> Turing-complete two stacks --> Turing-complete infinite tape --> Turing-complete heaps --> we don't really know monoids --> all kinds of interesting things And so on and so on. Note that you can also modify other elements: The alphabet -- make it infinite, or continuous. The transition function -- make it a relation, or allow $$\varepsilon$$-transitions. The state set -- make it infinite, or allow multiple starting states. The inputs -- make them infinite, or trees, or timed sequences. Additional restrictions -- use tapes but allow only movement in one direction, or allow to scan k times (alternating directions or always left-right?) Interesting things can happen! That's the beauty of mathematical definitions: you usually get something. Then you can spend many months on finding out what it is you got. Maybe it's interesting, maybe not. Maybe it's useful (a dreaded question after talks!), maybe not. But it always is. There are several possible layers to your question. Why must PDAs have a stack? -- By definition! That's just how it is. But why are they defined like that? -- Somebody thought it might turn out interesting. And apparently it did, because many people (read: the entire field) has agreed to use that definition. Why is it interesting? -- See reinierpost's answer. Why does my teacher choose to teach PDAs? -- That's a multi-facetted issue; see here for a similar question. The answers carry over. I'd like to expand on the second bullet a little. How do different definitions come about? If you take finite control with different memory models, the resulting classes of automata have very different capabilities. In fact, that's a huge part of what automata theory concerns itself with. Once you realize that playing around with definitions can lead to interesting concepts, it's only natural for researchers -- a curious bunch! -- to try and explore the space of possible models. To list just a few examples of ideas people have had: finite memory --> regular single stack --> context-free single queue --> Turing-complete two stacks --> Turing-complete infinite tape --> Turing-complete heaps --> we don't really know And so on and so on. Note that you can also modify other elements: The alphabet -- make it infinite, or continuous. The transition function -- make it a relation, or allow $$\varepsilon$$-transitions. The state set -- make it infinite, or allow multiple starting states. The inputs -- make them infinite, or trees, or timed sequences. Additional restrictions -- use tapes but allow only movement in one direction, or allow to scan k times (alternating directions or always left-right?) Interesting things can happen! That's the beauty of mathematical definitions: you usually get something. Then you can spend many months on finding out what it is you got. Maybe it's interesting, maybe not. Maybe it's useful (a dreaded question after talks!), maybe not. But it always is. There are several possible layers to your question. Why must PDAs have a stack? -- By definition! That's just how it is. But why are they defined like that? -- Somebody thought it might turn out interesting. And apparently it did, because many people (read: the entire field) has agreed to use that definition. Why is it interesting? -- See reinierpost's answer. Why does my teacher choose to teach PDAs? -- That's a multi-facetted issue; see here for a similar question. The answers carry over. I'd like to expand on the second bullet a little. How do different definitions come about? If you take finite control with different memory models, the resulting classes of automata have very different capabilities. In fact, that's a huge part of what automata theory concerns itself with. Once you realize that playing around with definitions can lead to interesting concepts, it's only natural for researchers -- a curious bunch! -- to try and explore the space of possible models. To list just a few examples of ideas people have had: finite memory --> regular single stack --> context-free single queue --> Turing-complete two stacks --> Turing-complete infinite tape --> Turing-complete heaps --> we don't really know monoids --> all kinds of interesting things And so on and so on. Note that you can also modify other elements: The alphabet -- make it infinite, or continuous. The transition function -- make it a relation, or allow $$\varepsilon$$-transitions. The state set -- make it infinite, or allow multiple starting states. The inputs -- make them infinite, or trees, or timed sequences. Additional restrictions -- use tapes but allow only movement in one direction, or allow to scan k times (alternating directions or always left-right?) Interesting things can happen! That's the beauty of mathematical definitions: you usually get something. Then you can spend many months on finding out what it is you got. Maybe it's interesting, maybe not. Maybe it's useful (a dreaded question after talks!), maybe not. But it always is. 2 added 1085 characters in body edited Oct 24 '18 at 10:19 Raphael♦ 59k2626 gold badges144144 silver badges327327 bronze badges There are several possible layers to your question. Why must PDAs have a stack? -- By definition! That's just how it is. But why are they defined like that? -- Somebody thought it might turn out interesting. And apparently it did, because many people (read: the entire field) has agreed to use that definition. Why is it interesting? -- See reinierpost's answer. Why does my teacher choose to teach PDAs? -- That's a multi-facetted issue; see here for a similar question. The answers carry over. I'd like to expand on the second bullet a little. How do different definitions come about? If you take finite control with different memory models, the resulting classes of automata have veryvery different capabilities. In fact, that's a huge part of what automata theory concerns itself with. Once you realize that playing around with definitions can lead to interesting concepts, it's only natural for researchers -- a curious bunch! -- to try and explore the space of possible models. JustTo list just a few examples of ideas people have had: finite memory --> regular single stack --> context-free single queue --> Turing-complete two stacks --> Turing-complete infinite tape --> Turing-complete heaps --> we don't really know And so on and so on. Note that you can also modify other elements: The alphabet -- make it infinite, or continuous. The transition function -- make it a relation, or allow $$\varepsilon$$-transitions. The state set -- make it infinite, or allow multiple starting states. The inputs -- make them infinite, or trees, or timed sequences. Additional restrictions -- use tapes but allow only movement in one direction, or allow to scan k times (alternating directions or always left-right?) Interesting things can happen! That's the beauty of mathematical definitions: you usually get something. Then you can spend many months on finding out what it is you got. Maybe it's interesting, maybe not. Maybe it's useful (a dreaded question after talks!), maybe not. But it always is. If you take finite control with different memory models, the resulting classes of automata have very different capabilities. In fact, that's a huge part of what automata theory concerns itself with. Just a few examples: finite memory --> regular single stack --> context-free single queue --> Turing-complete two stacks --> Turing-complete infinite tape --> Turing-complete heaps --> we don't really know And so on and so on. Note that you can also modify other elements: The alphabet -- make it infinite, or continuous. The transition function -- make it a relation, or allow $$\varepsilon$$-transitions. The state set -- make it infinite, or allow multiple starting states. The inputs -- make them infinite, or trees, or timed sequences. Interesting things can happen! That's the beauty of mathematical definitions: you usually get something. Then you can spend many months on finding out what it is you got. Maybe it's interesting, maybe not. Maybe it's useful (a dreaded question after talks!), maybe not. But it always is. There are several possible layers to your question. Why must PDAs have a stack? -- By definition! That's just how it is. But why are they defined like that? -- Somebody thought it might turn out interesting. And apparently it did, because many people (read: the entire field) has agreed to use that definition. Why is it interesting? -- See reinierpost's answer. Why does my teacher choose to teach PDAs? -- That's a multi-facetted issue; see here for a similar question. The answers carry over. I'd like to expand on the second bullet a little. How do different definitions come about? If you take finite control with different memory models, the resulting classes of automata have very different capabilities. In fact, that's a huge part of what automata theory concerns itself with. Once you realize that playing around with definitions can lead to interesting concepts, it's only natural for researchers -- a curious bunch! -- to try and explore the space of possible models. To list just a few examples of ideas people have had: finite memory --> regular single stack --> context-free single queue --> Turing-complete two stacks --> Turing-complete infinite tape --> Turing-complete heaps --> we don't really know And so on and so on. Note that you can also modify other elements: The alphabet -- make it infinite, or continuous. The transition function -- make it a relation, or allow $$\varepsilon$$-transitions. The state set -- make it infinite, or allow multiple starting states. The inputs -- make them infinite, or trees, or timed sequences. Additional restrictions -- use tapes but allow only movement in one direction, or allow to scan k times (alternating directions or always left-right?) Interesting things can happen! That's the beauty of mathematical definitions: you usually get something. Then you can spend many months on finding out what it is you got. Maybe it's interesting, maybe not. Maybe it's useful (a dreaded question after talks!), maybe not. But it always is. 1 answered Oct 23 '18 at 19:34 Raphael♦ 59k2626 gold badges144144 silver badges327327 bronze badges If you take finite control with different memory models, the resulting classes of automata have very different capabilities. In fact, that's a huge part of what automata theory concerns itself with. Just a few examples: finite memory --> regular single stack --> context-free single queue --> Turing-complete two stacks --> Turing-complete infinite tape --> Turing-complete heaps --> we don't really know And so on and so on. Note that you can also modify other elements: The alphabet -- make it infinite, or continuous. The transition function -- make it a relation, or allow $$\varepsilon$$-transitions. The state set -- make it infinite, or allow multiple starting states. The inputs -- make them infinite, or trees, or timed sequences. Interesting things can happen! That's the beauty of mathematical definitions: you usually get something. Then you can spend many months on finding out what it is you got. Maybe it's interesting, maybe not. Maybe it's useful (a dreaded question after talks!), maybe not. But it always is.