Ok so I'm having difficulty understanding how to Take a regular expression and turn it into a finite state machine..

so heres a problem similar to the one I need to solve..

Say I have a machine that takes £1 coins, dispenses beer(£1) and water(£2)

so the values for a regular expression are;

p = inserting a coin
c = dispense beer
b = dispense water
(Also buttons to dispense cans)
B = beer button
W = water button

and lets say ppWb represents buying water..


REG = (pBc+p(e+p)Wb)* (e is an empty string..)

so how do I derive this into a finite state machine? I can vaguely turn this into a syntax tree, then where do I go from there?

If anyone could give a rough sketch I'd be really grateful..

Hi there,

Basically, all you have to do is draw all the possible transitions between the different states. So, for example, begin at start, then to a state with one coin inserted, one with B-button pushed, the corresponding output, and from there back to start.

(start) -> (p) -> (B:dispense beer) -> (start)
Then from the single coin state draw another transition to a state for two coins and from there to water & output and back to start.

(p) -> (p2) -> (W:dispense water) -> (start)
Perhaps to clarify some of the drawing: a stamp dispenser.

Once you have a drawing it will be much easier to translate those transitions into some workable code (for example, something like Prolog).

Hope this helps, good luck!