Thread: 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]

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.