2
$\begingroup$

I'm attepting to model a process flow where the transition to the next state is occasionally based on not only the input to the current state, but a prior state as well.

Below is an example graph descibring the process. The essence is: If both State Q1 and State Q3 recieve an input of one, after State 3, transition to State Q4, otherwise transition to State Q5.

Non-state dependent machine

I understand that it would be possible to model this using a finite-state machine where we duplicate any states between those that we are interested in. The example below demonstrates this with States Q2a and Q2b corresponding to the differences in input at state Q1

State-dependent

However, as the number of conditions and the gaps between them grows (both of which are possible in the process I'm looking at), the number of states grows exponentially.

The question is, what other computational models could be used to describe a process where an arbitrary number of inputs could be used to control transition between states?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It sounds like you aren't looking for a different model, per se, just a standard way to compactly represent these scenarios in diagrams. For that, I think it's fairly common to use regular expressions to label transitions, but I'm not sure this captures what you intend. The real answer is that you might need to get into machine models like pushdown automata, perhaps even Turing machines, to really get what you want: a machine that has access to the already-consumed input stream. What you're describing would be easy to capture by pushing and popping stack symbols, for instance. $\endgroup$
    – Patrick87
    Commented Jul 22, 2013 at 1:13
  • 1
    $\begingroup$ Where does your original state machine come from? Shouldn't the states be derived from how the machine interacts with its environment? That would directly produce the second model. $\endgroup$
    – reinierpost
    Commented Jul 22, 2013 at 9:01

2 Answers 2

Reset to default
2
$\begingroup$

In digital design we would call the thing you are looking for an algorithmic state machine. In compiler design we would call it a control flow graph. The idea in either case is that you divide the state problem into two parts, one part represents the control state, the other part represents the data path. You label the states with how you want the data path to be modified, and the data path has some boolean outputs that you use to determine which way the control state should change.

Formally, you are describing a Moore machine where each state describes a set of control signals that will be sent to tell the data path how to modify itself, and the data-path in turn has a small set of boolean outputs that are used as the input language to the control state machine.

Your original problem would then have a control state, Q, and two variables, v1 and v2 and the graph would look something like:

       q1: v1 <- some_function(...)
                |
                v
       q2: something else happens
                |
                v
    q3: v3 <- some_other_function(...)
        test (v1==1 && v3==1)?
       /                 \
       | true             | false
       v                  v
q4: something    q5: something else
       \                  /
        \                /
         v              v
           q6: whatever
Improve this answer
$\endgroup$
1
$\begingroup$

In Petri nets, state is distributed; basically, there is no distinction between state transitions and messages. This allows a much more compact representation of certain types of systems, which may or may not include the sorts of systems you are trying to model. They may be particularly useful if your inputs and output signals cannot queue up.

Improve this answer
$\endgroup$

Your Answer

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