A theory question: FSA

This is a discussion on A theory question: FSA within the A Brief History of Cprogramming.com forums, part of the Community Boards category; This doesn't really apply to any specific language, platform, or API, so I decided to place this question here in ...

  1. #1
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738

    A theory question: FSA

    This doesn't really apply to any specific language, platform, or API, so I decided to place this question here in GD. This was a question posed to us by my CS professor from my CS computational theory class.

    This is a theory question concerning Finite-State Automata or Finite-State Machines.

    Image a machine that looks like such:

    FSA System: Marble-Rolling Toy

    A marble is dropped from either slot A or B. x1, x2, and x3 are levers that cause the marble to fall either to the left or to the right. Whenever the marble encounters a lever, it causes the lever to reverse after the marble passes, so the next marble will take the opposite branch.

    My professor told us to construct a state transition diagram of FSA. This is what I constructed:

    FSA state transition diagram

    The part I was wondering about, did I make a mistake by putting the extra "left" and "right" labels onto the x1, x2, and x3 levers in the diagram? It is the only way I could think of doing this. Is there a way to draw a deterministic FSA transition diagram without doing that?

    I could very easily do a non-deterministic FSA diagram without putting the "left" and "right" labels onto the x1, x2, and x3 levers, but he specifically asked for a deterministic diagram.

    This was the only way I could think of doing it. Anyone familiar enough with FSA to confirm that?

    [edit]

    q1 is the beginning state.
    q5 is the accepting state, and q6 is a non-accepting state.

    [/edit]
    Last edited by DavidP; 01-21-2007 at 05:16 PM.
    My Website

    "Circular logic is good because it is."

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Whether or not you can label edges is convention IMHO. You could also have "Left of X1", "Right of X1" as states if you don't want the labels.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    It looks like you've misinterpreted the problem.

    The marble game itself is a state machine, with 8 different states, one for each possible combination of L or R for each xn.

    Let us label the states by notation
    <x1><x2><x3>, so for example, if x1 is sloping right, x2 is sloping left, x3 is sloping right, then we name that state "RLR"

    The marble.jpg shows the machine in state "LLL".


    From state LLL, there are two transitions, "A", and "B".
    "LLL" transitions by B to "LRR". Note that we don't care which pipe it comes out of (C or D).
    "LRR" transitions by B to "LRL".
    "LRL" transitions by A to "RRL".

    Basically... by the nature of the machine, you know that your end result will have 8 states ("LLL", "LLR", "LRL", "LRR", &ct.), and each state will have 2 transitions (1 for "A", 1 for "B").

    There is no starting or accepting state, don't worry about those. It's a cyclical machine.
    Callou collei we'll code the way
    Of prime numbers and pings!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. another do while question
    By kbpsu in forum C++ Programming
    Replies: 3
    Last Post: 03-23-2009, 01:14 PM
  2. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 10:47 PM
  3. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 09:22 PM
  4. Theory question...
    By Imperito in forum C++ Programming
    Replies: 1
    Last Post: 01-01-2003, 05:58 AM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 01:47 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21