As a simple example, try to make an FSM (which will have a fixed number n states) for matching parentheses – then I can always make a parenthesized expression of a certain size that your FSM cannot match. So you try to add some states to the FSM, now it can handle that expression. But then I wrap the expression in more parentheses and your FSM fails. However, a computer (or turing machine – or in this case even a pushdown automaton) can always match it.
(But the limitations of FSM's are also strengths – just like some people like to keep parts of their programs pure or free of I/O and feel safe when their compiler can check that, you know that the FSM itself won't eat your memory, and has a bunch of other provable characteristics.)
The point I'm trying to make is not that FSM actually can do these, but rather that this distinction is largely theoretical. In practice, even linearly bounded isn't practical because of course I can pick a sufficiently large input that will run out of tape: there's only so much information storage in the universe.
No. That is simply not true. See https://en.wikipedia.org/wiki/Chomsky_hierarchy#The_hierarch...
As a simple example, try to make an FSM (which will have a fixed number n states) for matching parentheses – then I can always make a parenthesized expression of a certain size that your FSM cannot match. So you try to add some states to the FSM, now it can handle that expression. But then I wrap the expression in more parentheses and your FSM fails. However, a computer (or turing machine – or in this case even a pushdown automaton) can always match it.
(But the limitations of FSM's are also strengths – just like some people like to keep parts of their programs pure or free of I/O and feel safe when their compiler can check that, you know that the FSM itself won't eat your memory, and has a bunch of other provable characteristics.)