0
\$\begingroup\$

Consider the two following definitions:
Discrete Deterministic System: a system where inputs and outputs can have only a finite number of values, and is deterministic;
Finite State Machine: an abstract machine that can be in exactly one of a finite number of states at any given time.

My understanding is that the states in a discrete deterministic system will be a combination of the actual inputs (and possibly previous ones, if it is a system with memory), and therefore the number of states should be finite.

Provided that complexity is not a problem, is it be possible to build a finite state machine that models every possible discrete deterministic system?

If not, can you provide an example of a discrete deterministic system that cannot be represented as a finite state machine?

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I would think that you must also require the discrete system to be deterministic to make it representable with an FSM. \$\endgroup\$
    – Elliot Alderson
    Apr 1, 2019 at 12:35
  • \$\begingroup\$ @ElliotAlderson That's a very good point that I have missed. \$\endgroup\$
    – Dmitry Grigoryev
    Apr 2, 2019 at 8:11
  • \$\begingroup\$ @ElliotAlderson Maybe a nondeterministic state machine could be used to model stochastic systems. Anyway, when I asked the question I was indeed thinking about deterministic systems, so I edited it. Thank you. \$\endgroup\$
    – Isacco
    Apr 2, 2019 at 14:19
  • \$\begingroup\$ @Isacco No. Non-deterministic FSMs are equivalent to deterministic FSMs. The non-determinism of these is meaning something else. \$\endgroup\$
    – Eugene Sh.
    Apr 2, 2019 at 14:20

1 Answer 1

Reset to default
2
\$\begingroup\$

Any real discrete system will have a finite number of memory cells (and a finite number of states as a consequence), so it can be theoretically represented by a finite state machine.

If we also consider abstractions, then a PDA or a Turing machine are examples of discrete systems with infinite number of states.

I mention abstractions because they can represent some real systems for which FSMs are useless, even if strictly speaking such abstractions cannot be implemented in silicon. For example, a theoretical FSM representing a micro-controller with 128 bytes of RAM will have more states than there are atoms in the known universe. Representing such an MCU with a state machine is practically impossible, and if stack overflows are avoided in the implementation, I'd call it a PDA rather than an FSM.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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