DavidP

01-21-2007, 05:14 PM

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 (http://students.cs.byu.edu/~dpru/images/marble.JPG)

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 (http://students.cs.byu.edu/~dpru/images/fsa.JPG)

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?

q1 is the beginning state.

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

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 (http://students.cs.byu.edu/~dpru/images/marble.JPG)

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 (http://students.cs.byu.edu/~dpru/images/fsa.JPG)

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?

q1 is the beginning state.

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