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

Back to your regular expression.
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:
First road: pBC
Second road: pWb
Third road: ppWb
[/code]

 Bookmarks
##### Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement