3 ms·
> State machines and finite automata are two different things Author says that SMs and "finite automata" are different things, and links to Wikipedia to prove
by denton-scratch 4y ago
> State machines and finite automata are two different things
Author says that SMs and "finite automata" are different things, and links to Wikipedia to prove it. But Wikipedia says "A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation."
https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Finite-state_machine
Author seems to take the view that something like a compiler is a "state machine", or at least can be modeled as one. I suspect that his definition (which he doesn't actually set out) translates roughly to "machine".
- comfypotato 4y agoGood catch. The author directly contradicts themselves here. Can’t help but wonder if the rest is worth reading now.
- afiori 4y agoFinite state machines are equivalent to finite automaton, but non finite state machines are not. The most obvious difference is that a state machine can have infinite transitions and infinite states. The most obvious example is a counter machine that simply keep tracks of how many events it received. Such state machines can be Turing complete, but also allow to add restrictions to limit their expressiveness https://en.m.wikipedia.org/wiki/Pushdown_automaton https://en.m.wikipedia.org/wiki/Pushdown_automaton Edit: to add more context Turing machines are essentially finite state machines with an unlimited memory attached and specific input events (the alphabet of the memory eg bits) and output states (move left/right, write, halt; with possibly multiple state for each output)