Can a finite state machine transition to a previous state?

Question

I know that a FSM can transition to the next state and even to the current state, i.e. a state that transitions to itself, but is it legal to have a state transition to a previous state (state C transition to state B)?

Answer 1

Yes, many practical FSMs will in fact do this. Consider an FSM that identifies valid strings of number separated by one or more spaces. This would start in the "digit" state and at some point transition to the "space" state from which it might well transition back to the "digit" state.

Answer 2

The "next state" of an FSM is defined as the state the machine will transition to in the next "time slice" or when the next input arrives, or whatever.

Thus defined, the next state of C can be C itself, B, A, D, ZORG or whatever state you have in the machine. Alphabetical letters don't define what's previous and what's next, only the logical flow of the FSM.

This state machine from the Wikipedia page:

http://en.wikipedia.org/wiki/File%3AFinite%5Fstate%5Fmachine%5Fexample%5Fwith%5Fcomments.svg