(via drawohara)

(via drawohara)
I recently applied this great plugin a few times to tackle different tasks and would like to share with you the joys of thinking in state machines!
Disclaimer: This installment is ‘just’ an intro to the topic (a teaser if you like), it doesn’t contain actual instructions or code on how to use acts_as_state_machine – that comes in part II. Though the original intent was to write up a small tutorial with some example code, I started with an intro and the article grew so long that I decided to split it up – so stay tuned for part deux!
A finite state machine (FSM for short) a.k.a. finite state automaton (FSA) is a 5-tuple (Σ,S,s0,δ,F)… OK, just kidding. I doubt too much people are interested in the rigorous definition of the FSM (for the rest, here it is), so let’s see a more down-to earth description.
According to wikipedia, Finite state machine is “_a model of behavior composed of a finite number of states, transitions between those states, and actions_”. Somewhat better than those gammas and sigmas and stuff but if you are not the abstract thinker type, it might take some time to wrap your brain around it. I believe a good example can help here!
Everybody knows and loves regular expressions – but probably it’s not that wide known fact that regular expression matching can be solved with an FSM (and in fact, a lot of implementations are using some kind of FSM on steroids). So let’s see a simple example. Suppose we would like to match a string against the following, simple regexp:
ab+(a|c)b*
First we have to construct the FSM, which will be fed with the string we would like to match. An FSM for the above regular expression might look like this:
String matching against this FSM is basically answering the question ‘starting from the initial state, can we reach the finish after feeding the FSM the whole string?’. Pretty easy – the only thing we have to define is ‘feeding’.
So let’s take the string ‘abbbcbbb’ as an example and feed the FSM! The process looks like this:
Let’s see a very simple non-matching example on the string ‘abac’
Of course the real-life scenarios are much more complicated than the above one and sometimes FSMs are not enough (for example to my knowledge it’s not possible to tell about a number whether it is prime or not with a vanilla FSM – but a regexp doing just that has been floating around some time ago) but to illustrate the concept this example served fine.
Well, yeah, you are obviously not going to model an FSM the next time you would like to match a regexp – that would be wheel-reinvention at it’s finest. However there are some practical scenarios where an FSM can come handy:
Some real life examples of FSM usage in the Ruby/Rails world are why the lucky stiff’s Hpricot (using Ragel) or Rick Olson’s restful authentication plugin (using acts_as_state_machine)
In the next installment I’d like to focus on the practical usage of the acts_as_state_machine plugin – I’ll attempt to create an asynchronous messaging system in a Rails app using it.