> No, general-purpose computers are Finite Turing Machines, not Finite State Machines.
I am afraid a "Finite Turing Machine" is not a commonly used term, so I am not sure what you are saying here. Regardless, any general purpose computer is trivially an FSM, given their finite alphabets and states.
Er, sorry, I meant deterministic Turing machine, not finite. However, a general purpose computer is not a FSM, because a FSM only has one symbol worth of state (the currently selected state). A PDA adds a last-in-first-out stack. A TM replaces the stack with a seekable tape. A general-purpose computer has random-access storage.
> These two formalisms are TWO tiers of computing power apart, with Push-Down Automata existing in between.
The latter have infinite stacks, a luxury that current general-purpose computers cannot afford.
General-purpose computers can simulate infinite stacks/tapes using arbitrary attachable storage. If it runs out, it prompts the user to provide more storage. This means that any algorithm that can be evaluated by a TM can be evaluated by a modern general-purpose computer, with no fixed limits.
Coming back to the subject, it is possible to parse just about any grammar with a FSM, given that the input string shall not be longer than a fixed N characters. But it may be (far) more practical to use a different formalism in many cases.
This is trivially true, as you can always construct an FSM with O(k^n) states that hard-codes every possible valid input of length n or less. However, that disgusting complexity means that defining the FSM requires exponential space, which isn't STRICTLY in contradiction with the intent of working within bounded space, but it does a valiant job of TRYING to violate it.
/s/ Adam
