# Thread: Syntax tree's to Finitie state machines..?

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

I'd really appreciate some help :?  2.

3. Originally Posted by blackout83
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?
Suppose we have
a+b
The state machine is
X_1 --a--> END
X_1 --b--> END
(i.e. there are two edge from X_1 to END)

ab is equivalent to
X_1 --a--> X_2 --b--> END

a* is equivalent to
END --a--> END
Why?
Because a* accepts the empty string so we HAVE to start from END.

REG = (pBc+p(e+p)Wb)*
Let's simplify it a bit:
REG = (p(Bc+(e+p)Wb))*

The empty string is accepted so we have to start from END.

Step1:
END -- p(Bc+(e+p)Wb) --> END

Step2:
END -- p --> X_1 --> Bc + (e+p)Wb --> END

Step3:
END -- p --> X_1 --> Bc --> END
X_1 --> (e+p)Wb --> END

Step4:
END -- p --> X_1 -- B --> X_2 -- c --> END
X_1 --> (e+p)Wb --> END

Step5:
END -- p --> X_1 -- B --> X_2 -- c --> END
X_1 --> (e+p) --> Y_1 --W--> Y_2 --b--> END

A little note.
'e' is a bit troublesome.
C --q--> A --> (e+p) --> B
is equivalent to
C --q--> A --e--> B
A --p--> B
The problem is that we don't want edges with 'e'.
The solution is this:
C --q--> B
C --q--> A --p--> B
Do you see what happened? Your machine is not deterministic because you have two edge with the same label q.
We could make it deterministic but that's a tough task.

Back to our problem.

Step6:
END -- p --> X_1 -- B --> X_2 -- c --> END
X_1 --e--> Y_1 --W--> Y_2 --b--> END
X_1 --p--> Y_1

Step7:
END -- p --> X_1 -- B --> X_2 -- c --> END
END -- p ---------------> Y_1 --W--> Y_2 --b--> END
X_1 --p--> Y_1

Note that:
(pBc+p(e+p)Wb)* ==
(pBc+peWb+ppWb)* ==
(pBc+pWb+ppWb)* ==
(p(Bc+Wb+pWb))*

If you look at Step7 you'll see the correspondence:  