Is there a name for an inverted state machine?

Question

I recently needed something like a state machine, but with a slightly different use case.

In general, I would say a state machine knows about a set of states, and different events. Depending on the current state and the event, a state machine is able to decide if this is a valid event for this state, and to which state it should transition to.

What I need is slightly different: Again, I have a state machine knowing some states, transitions and events, but it does tell me which events have to happen to transition to a certain state. I already implemented such a machine and posted it for code review.

So, while the first machine is able to tell in which state it is after an event, the second machine is able to tell what has to happen to transition to a state.

According to this, my transition table looks different too. Instead of having new states in the intersection of current states and events, I'm storing the events in the intersection of current and new states.

Is there a name for this kind of inverted state machine, or is it just another implementation of a finite state machine?

Answer 1

If I understand you correctly, you could achieve this using transducers (i.e. automata which also produce outputs when taking a transition).

Suppose we are given a DFA $A = (Q,q_0,\Sigma,\delta)$ describing which events lead to which state transitions. Here $Q$ is the set of states, $q_0$ is the initial state, $\Sigma$ the alphabet of events, and $\delta:Q\times\Sigma\to Q$ the transition function. Then we can define a (nondeterministic) transducer $A'$ as $(Q,q_0,Q,\Sigma,\delta')$ as follows:

• $Q$ is the same set of states as before, and $q_0$ is still initial;
• The input alphabet is now also $Q$ (representing the target state you are trying to reach);
• $\Sigma$ is now the output alphabet;
• The transition relation $\delta'$ contains a tuple $(q,\delta(q,a),a,\delta(q,a))$ for each $q\in Q$ and $a\in\Sigma$ (representing the fact that to get from $q$ to $r$, you can use $a$ if $r=\delta(q,a)$).

Note that I'm assuming that you actually want to proceed to the given target state, otherwise you need to adapt the transition relation. Also, if there is no transition from $q$ to $r$, the computation simply fails; you may want to handle this case differently.

Answer 2

To me, it really seems to be just a definitional variation, not a different kind of computational model.

One could define the transition function of a DFA using $\delta:Q\times Q \to \mathcal{P}(\Sigma)$, instead of the more conventional $\delta:Q\times\Sigma\to Q$. The reason we don't usually do it is because it is awkward when you want to define a language, but it is possible to imagine a different application for which this would be a more suitable definition.

Answer 3

What you have described is not a state machine. Look at the problem this way: a state machine makes only choise at each step.

In your case there may be several choises (exponential large number of choises potentially). Your machine is more complex, as I see this it is a stack machine (a stack is required to a backtracking implementation).

Answer 4

Looking at your code, I think you may be looking for model-based testing.

In model-based testing, you create a model: an explicit declarative specification of the behavior expected from your system. This is what your line

    StateMachine<Human> fsm = StateMachineBuilder.create(Human.class)
            .from(Human.UNBORN).to(Human.BORN).to(Human.DEAD, this::died)
            .from(Human.BORN).to(Human.KID).to(Human.DEAD, this::died)
            .from(Human.KID).to(Human.ADULT).to(Human.DEAD, this::died)
            .from(Human.ADULT).to(Human.DEAD).startAt(Human.UNBORN);

looks like to me. You then generate test cases from the model and run the actual system against the test cases to determine whether the system complies with the model. Or you develop test cases on the fly, while you test. There are many different ways for specifying models and many different ways to generate test cases from models; for some variants, software is available to generate test cases automatically. This is a whole field.

So I think model-based testing is where you can find terminology to describe what you are trying to do, and perhaps even ready-made software that supports testing in the way you want to do it. One tool I've seen, although I've never used it, is JTorX.

Answer 5

If I understand correctly, you are dealing with a machine with states, and deterministic transitions to other states caused by events. This is an FSM.

Such an automaton is described by a state/event matrix, whatever the way transition data is supplied.