I know finite-state machines can be used to solve yes/no kind of problems, such as finding whether a word is in language or not. Can somebody tell me exactly what FSM cannot do and why?

  • Are you asking about more powerful deciders, or other tasks? See here or here, respectively. – Raphael Sep 3 '13 at 10:28

The answer depends on what you mean by FSM.

If by FSM you mean finite automaton, then there's a lot that it can't do. As others have pointed out, you can't remember more than a constant amount of information using a finite automaton; the memory must be encoded in the state. This means you can't do things like recognize $a^nb^n$, since you'd need to remember how many $a$ symbols you've seen, which is not possible unless you have an arbitrary amount of memory. The pumping lemma for regular languages and, especially, the Myhill-Nerode theorem offer insight into the kinds of things that can and cannot be done.

If by FSM you mean any automaton formalism which is limited to using finitely many states, then Turing machines are among the most computationally capable FSM models available. Indeed, anything which is effectively computable is computable by a Turing machine, according to the Church-Turing thesis. However, there are still limitations to what a Turing machine can decide: there are problems it cannot answer, such as the halting problem.

Models which aren't limited to a finite number of states aren't particularly interesting for a few reasons, most prominent of which are the following: they are of limited practical importance since we cannot construct real computers with infinitely many configurations; any language can be recognized in such a model by mapping strings in the language to unique accepting states, and strings not in the language to unique non-accepting states.

  • Another concern with infinite state-space is that such automata are hard to write down. – Raphael Sep 4 '13 at 9:27

Finite state machines can recognize regular languages. The canonical example for a language that can't be recognized by such an automaton is $L=\{a^nb^n\,|\, n\in \mathbb{N}\}$.

Depending on your exact definition of finite state machine, the model also includes things like timed automata, and Moore automata which are more powerful.

FSM doesn't have memory, It can't remember the things unlike Push Down Automata (i.e nothing but a FSM with Memory).Anything which require memory can't accepted by FSM.

  • 3
    Wrong. Constant-sized memory is readily available. – Raphael Sep 3 '13 at 12:30

It cannot even recognize palindromes and context free languages. I think you'll like this article that gives formal proofs and talks about limitations of FSM.

Also this is a very good article on Limitations of Computing. Since you are talking about FSMs, I think the topics here will interest you too.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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