is it valid that a state machine can have more than one possible state for some transition?

Question

I have a requirement for a workflow which I am trying to model as a state machine, I see that there is more than one outcome of a given transition(or activity).

Is it valid for a state machine to have more than one possible states, but only one state will be true at a given time?

Note: This is my first attempt to model a state machine.

Eg. might be:

s1->t1->s2

s1->t1->s3

s1->t1->s4

where s1, s2, s3, s4 are states and t1 is transition/activity.

A fictitious real world example might be:

For a human, there can be two states: hungry, not hungry A basket can have only one item from: apple, orange.

So, to model it we will have:

hungry->pick from basket->apple found

hungry->pick from basket->orange found

apple found->eat->not hungry

orange found->take juice out of it and then drink-> not hungry

Answer 1

Yes, you can have that.

In automata theory, people call it non-deterministic state machine.

From the Wikipedia article:

In automata theory, a nondeterministic finite automaton (NFA), or nondeterministic finite state machine, is a finite state machine that:
(1) does not require input symbols for state transitions and
(2) is capable of transitioning to zero or two or more states for a given start state and input symbol.
This distinguishes it from a deterministic finite automaton (DFA), in which all transitions are uniquely determined and in which an input symbol is required for all state transitions. Although NFA and DFA have distinct definitions, all NFAs can be translated to equivalent DFAs using the subset construction algorithm

Answer 2

The thing to recognize is you don't have to make all the states exactly model a real-world state, and you don't have to make all the transitions exactly model a real-world action.

For your example, you can fix it in one of two ways: create a separate transition for each possible outcome, or create an intermediate state. Creating a separate transition looks like this:

• hungry -> pick orange from basket -> have orange
• hungry -> pick apple from basket -> have apple

Here, you basically don't follow the transition until you've determined what fruit you picked. It's non-deterministic in the real world, but in your model you discover which event occurred before you update your state machine.

The intermediate state fix looks like this:

• hungry -> pick item from basket -> have item
• have item -> identify item as orange -> have orange
• have item -> identify item as apple -> have apple

Here, you can follow the first transition without knowing what fruit you've picked, but then you immediately identify it and make another transition. This more closely models the real-world actions, but recognizes that picking and identifying are two separate actions, even though they occur almost simultaneously so humans don't really think of them as separate.

Which method you choose depends on the implementation. You might want to try implementing both and see which comes out cleaner in your situation.

Answer 3

What you are looking for is not a state machine, but a petri net. It is actually more common for workflows to be modeled using petri nets, than it is using a state machine.

And one thing I want to point out: In correct workflow, one activity can only produce one type of output. In your case, you are probably having different activities producing different outputs. Or at least something that starts as single activity, but soon branches out into different activities. It really doesn't make much sense for same activity to produce different results at different executions.