lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


On Thu, Mar 28, 2019 at 8:32 PM Coda Highland <chighland@gmail.com> wrote:

> 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.

> 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.

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.

Cheers,
V.