[ones_and_zeros]

Noob question but what about state machines where a given state could transition to more than one other state depending on some outside factors? Or is that no longer considered a state machine?

For a relevant to me example, a VM state. A VM in running state could be transitioned to terminated or stopped or hibernating depending on an admins action.

[jononor]

Your example is a standard Finite State Machine. Multiple possible transitions is the norm for an FSM, and each possible transition is guarded by some predicate which decides if it should be followed.

# transition notation: FromState -predicate-> ToState

    Running -stop_button-> Stopped
    Stopped -start_button-> Running
    Running -start_button-> Running # stay running
    Stopped -stop_button-> Stopped # stay stopped

The stop/start_button button here can either be events that come in from the outside (from dedicated click handlers in a GUI), or be functions or properties that are polled when evaluating next().

Since booting a VM can take quite some time, one might want to introduce a Starting state between Stopped and Running.

The example in the original article is just a special case, where there is only one possible transition from each state, and where the predicate always returns true. Although arguably for a real traffic light, there should be a predicate on the transition that checks that enough time has passed! At least I would model that as part of the FSM, instead of on the outside.

EDIT: fix formatting

[jimsmart]

Harel's Statecharts (an evolution of state machines) have concurrent states (with branch/fork and merge/wait), which would be one way of solving what you describe.

I believe Harel may have borrowed concurrent (aka orthogonal) states from elsewhere though: state machines have been extended a few different ways over the years.

So you may find similar features elsewhere too.

[jimsmart]

> A VM in running state could be transitioned to terminated or stopped or hibernating depending on an admins action.

Actually, that doesn't necessarily need concurrency, I misread your question.

Yes, in a state machine, each state can have different conditions (guards) on each outgoing transition. So when running, pushing the stop button would cause transition to the stop/stopping state, pushing the pause button would transition to the pause/pausing state.

Guard conditions are simple boolean decisions, based upon events or other state. And sure, that event/state could be triggered externally to the state machine.

Technically it might not be a 'pure' state machine, but they rarely are outside of toy examples, in my experience — they always have to interact with something, and that thing is often not a state machine. Arguably I'm splitting hairs over philosophical differences here, but hey.

[Tyr42]

You might queue up events which cause it to transition to another state. If you hit the hibernate button, it might finish rendering the current frame before checking to see if the button was pressed, then hibernate. So it's the same state machine just with a larger input space.

[ones_and_zeros]

Sure but how does that work with the provided implementation where all states can only transition to a single state, this is ensured at compile time. What does the code look like that allows a state to transition to one of several other states?

[skrtskrt]

No Rust, but here's a Python implementation that I have built on top of before: https://github.com/pytransitions/transitions

You add the concept of finite "triggers", where [state i] + [trigger result j] always takes you to [new state](which could be the same state if you want)

Triggers are just functions where anything could be happening - coin flip, API call, but they return one of an enumerated set of results so the machine can always use their result to go to another state.

[ones_and_zeros]

Ah ok. I don't write Rust either but maybe it'd look like:

  impl State<Running> {
    pub fn next(self, Trigger<Hibernate>) -> State<Hibernate> {
        State { _inner: Hibernate {} }
    }

    pub fn next(self, Trigger<Terminate>) -> State<Terminate> {
        State { _inner: Terminate {} }
    }
  }

[imtringued]

Usually you would just call your functions hibernate() and terminate(). That way you can call hibernate() on State<Running> but not on State<Terminated> or State<Hibernate>.

[uryga]

that's known as an NFA (Nondeterministic Finite Automaton), a variant of FSMs.

[jononor]

Nondeterminism not needed (or desired I think :D) for an FSM that can turn a VM on or off based on start/stop buttons. Its just multiple possible transitions, guarded by different conditions (the buttons).

But yeah, Nondeterministic FSMs are possible. Ie based on a transition probability.

[uryga]

the "nondeterminism" here doesn't mean we're dealing with probabilities, it's a more discrete kind - it just means that instead of

  S1 --a--> S2

you can have

  S1 --a--> S2
    '--a--> S3
    '--a--> S4

i.e. transition to multiple states "at once"¹. then, instead of being in one state, like an FSM, your NFA is in a set of states, like it had multiple threads, and proceeds "in parallel" from each state. probably not the best explanation, but i'm sure you can find good material about this.

---

¹ this a way to represent nondeterminism in a pure/math-y setting: instead of

  def f():
    b = random_bool()
    if b:
      res = "yes"
    else:
      res = "no"
    return res

you do

  def random_bool2():
    return {True, False}

  def f2():
    res = set()
    for b in random_bool2():
      if b:
        res.add("yes")
      else:
        res.add("no")
    return res

or just:

  def f2():
    return {"yes", "no"}

i.e enumerate all the possible results f() could give depending on what `random_bool()` returns.