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?

  • 3
    $\begingroup$ With infinitely many states you can recognize all languages (over a finite alphabet). It is just a less interesting concept. $\endgroup$
    – plop
    Dec 2 '20 at 16:12
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 2 '20 at 16:38

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 "infinite state machine" 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.

  • $\begingroup$ Thank You. I have got it now. $\endgroup$
    – SrJ
    Dec 2 '20 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.