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

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:

apple found->eat->not hungry

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

• How do you decide which transition to follow? – user7043 Jun 6 '14 at 7:29

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

• would you mind explaining more on what it does and why do you recommend it as answering the question asked? "Link-only answers" are not quite welcome at Stack Exchange – gnat Jun 6 '14 at 13:30

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.

• This is really the best answer. A state machine "should" contain a state representing every ... state. "Having an apple" is a different state than "having an orange" and they shouldn't be modeled as the though they were the same. You could, of course, but then you lose the deterministic nature of a state machine, and with it most of the value -- the ability to reason about the machine with certainty. – Dan Homerick Jul 18 '18 at 15:17
• Karl, Are the "have item" states the same as substates? – johnny Aug 7 '18 at 20:45
• No, different concept. Substates are more of an encapsulation of states within other states. This is a transition on the same level of the hierarchy. – Karl Bielefeldt Aug 7 '18 at 20:57

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.

• So how should the above example(the basket one) be modeled? – shankbond Jun 6 '14 at 11:07
• @shankbond Why are you making the model? Are you going to use it to run the process or are you trying to simulate it? – Euphoric Jun 6 '14 at 13:09
• Perhaps only one type of output, but an item can have one of several states following the current one? Just think of have an issue "in progress". You may decide not to work on it anymore and its state returns to "open". And when you do finish working on it, it's state may become "fixed", or "working as designed", or "cannot reproduce" or... How about the output of working on an issue, given that it can transition to all these states? It may be documentation, a working feature [+ doc], or nothing at all? How would you deal with a "working on an issue" activity to satisfy the one output rule? – Marjan Venema Jun 6 '14 at 13:55
• @Euphoric the above example is just a sample, to demonstrate the process when a person is hungry to when a person is not hungry :) But in real life I want to model a process with many conditional branches (if-else). – shankbond Jun 11 '14 at 16:15