Why can PDAs have infinite stack but FSMs cannot have infinite state? A Finite State Machine cannot accept the language
$$L = \{ 0^n1^n \mid n &gt; 0  \} $$
because it will require infinite amount of memory to remember the number of zeros. But a Push Down Automaton can recognize it with an infinite stack.
Why are we allowing infinite storage for the stack of PDA but not for the states of an FSM? If we can do with an infinite stack, we can also do it with an infinite FSM. So, why is there no &quot;Infinite State Machine&quot;? What's the problem with it?
One of the crucial properties of a model of computation is that each automaton has a finite description. Both FSMs and PDAs have finite description. In contrast, an &quot;infinite state machine&quot; won't necessarily have a finite description, unless it is constrained somehow.
Also, as mentioned in the comments, an unconstrained infinite state machine can accept any language. Indeed, we can construct a machine whose states are $\Sigma^*$. We define the transition function so that after reading the word $w$, the machine is at state $w$. Thus, by choosing the accepting states, we can obtain any language, making the model uninteresting.