Take the 2-minute tour ×

I am stuck with a state machine that has the following problem:

State 1 ----transition 1---> State 2----transition 2---> State 3

State 4 ----transition 4---> State 2----transition 2---> State 3

Transition 1 is associated with action 1. Transition 4 is associated with action 4. However, after designing the entire machine, I realized that transition 2 can potentially be related with either action 2 or action 3 depending on whether the state prior to state 2 was state 1 or state 4 and consequently whether action 1 or action 4 was executed.

I tried working out a different design but was unable to do that. This is not a push automata too. What do I do in order to get this straightened out

share|improve this question
there is a possibility to add images to your question, be it from the web or from your computer. I think a .jpg could help here... –  woliveirajr Nov 17 '11 at 15:16
Thanks. I will have to scan to add image. I will try this over the weekend –  doon Nov 17 '11 at 18:01
Your state machine isn't valid. There is no initial state, and state4 can never be reached. In a state machine, only the current state and previous state can affect the action, not the previous state (unless you save that previous state on a stack, but you already said this isn't a PDA). –  Jon Dec 24 '13 at 11:02

1 Answer 1

It seems to me that what you are saying is that state 2 can actually be in one of two states, either preceded by state 1 or state 4. That says to me that it should actually be represented by two states, though both could proceed to state 3.

So, state 1 -> state 2 -> state 3, and state 4 -> (new) state 5 -> state 3.

Is there any reason you could not do that?

share|improve this answer
Thanks for your response. In terms of behavior, state 2 is EXACTLY the same as state 5. I have to say that state 2 is x_with_prev_state_as_state_1 and state 5 is state_x_with_prev_state_as_state_4. That is the only distinguishing aspect between the states. I think if I have to make such distinctions then there must be something wrong somewhere. I will try to come up with a concrete example without going on the horrific details of the system. Meanwhile, I thought about pushdown automata more, and it seems if in the stack I push down the previous state, then this system is modeled. Is it ok –  doon Nov 17 '11 at 16:23
What I'm saying is that if the previous state matters, then that indicates that it is in a different state depending on where it came from. The idea of the state machine is that all relevant information is contained in the current state, you don't need additional information like its predecessor. To say that two states are the same except for X, indicates that they are different states no matter what X is. –  Derek Nov 17 '11 at 16:28
@doon: I think this is the right way to do it. However, you can share the implementation between two states. Have the two state functions call the same underlying code. –  Zan Lynx Mar 15 '12 at 17:43

Your Answer


