# 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 > 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 "Infinite State Machine"? What's the problem with it?

• With infinitely many states you can recognize all languages (over a finite alphabet). It is just a less interesting concept. – plop Dec 2 '20 at 16:12
• It is better to say that a push-down automaton may use an unbounded amount of statck. There is no moment of execution in which the stack is actually infinite. – Andrej Bauer Dec 2 '20 at 16:38

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.