Notices
Results 1 to 2 of 2

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

  1. #1 Syntax tree's to Finitie state machines..? 
    New Member
    Join Date
    May 2009
    Posts
    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 :?


    Reply With Quote  
     

  2.  
     

  3. #2 Re: Syntax tree's to Finitie state machines..? 
    Forum Freshman
    Join Date
    May 2009
    Posts
    5
    Quote 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]


    Reply With Quote  
     

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
  •