0

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..

2
Contributors
1
Reply
2
Views
7 Years
Discussion Span
Last Post by Traevel
0

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! :)

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.