# Model marbel toy with finite automata

I'm resolving this question of Hopcroft and et al Book. Figure 1 below is a marble rolling-toy. A marble is dropped at A or B. Levers $x_1,x_2$ and $x_3$ cause the marble to fall either to the left or to the right. Whenever a marble encounters a lever, it causes the lever to reverse after the marble passes, so the next will take the opposite branch.

I got resolve the question ...

a)Model this toy by finite automaton: To model this toy, a state is represented as sequence of three bits followed by r or a (previous input rejected or accepted). For instance, 010a, means left, right, left, accepted. Then the Transition table is

b)Informally describe the language of the automaton

but not b) question. How I will be able to resolve this question?

EDIT I see a solution here I modify my question using suggestions and that solution. According that solution exist a case:

Penultimate configuration interrupts is * \ / , where * means / or \; and the ending is 1 and X mod 4 = 0, or (X-3) mod 4 = 0 (X is the numbers of 0's and 1's).

For my question, from this case I get the subcase

Penultimate configuration interrupts is * \ / , where * means / or \; and the ending is 1 and X mod 4 = 0.

Then, the restrictions are: the number of 1's, without the ending, is even and the number of 0's is impar. I will be able to verify that configuration with that restrictions for few instances, but How I will be able to demonstrate that the $x_2$ interrupt configuration is \?

• What have you tried? Have you tried writing out the strings in the language (all strings of length 1, of length 2, of length 3, etc.)? Also, I suggest you model the automaton differently. I don't know what it means to say "input rejected". It seems to me you should think of this as a language over alphabet $\{A,B,C,D\}^*$, where $A,B$ indicate a marble dropped at either position $A$ or $B$ and where $C$ or $D$ indicate a marble coming out at position $C$ or $D$. The 0/1 business is an internal detail that's not part of the externally visible behavior of the system.
– D.W.
Commented Jun 4, 2014 at 15:49
• @D.W. The problem statement in the text says it more clearly: "nonacceptance represents a marble exiting at $C$". While it's partially correct to say that the internal details aren't part of the externally visible behavior of the system, such a point of view obscures the intent of the problem, to see this system as a finite automaton and then ask which sequences of $A$s and $B$s leave the system in an accepting state. For example, the first few accepted strings are $BB, AAB, ABA, ABB, BAA, BAB, BBB, AAAA, AAAB, \dots$. Commented Jun 4, 2014 at 20:29

Count $A$'s and $B$'s. The next $A$ will only exit at $D$ iff the first two levers are in right position. When does that happen? The first lever toggles at every $A$, but the second lever interacts with the $B$'s.
At the same time, the situation for $B$ is symmetric. The next $B$ will not exit $D$ only if both levers are left. When does that happen?
• I consider three cases depending where fall the last marble: 1)All strings ending in a 1, where the number of 1s is even. 2)All strings end in a 1. 3) All strings with even number of 0s but I don't found any rule. The cases 1 is easy but the other I don't understand when the $x_2$ marble is on right. Commented Jun 24, 2014 at 7:24
• The position of $x_2$ depends on both the number of $A$'s and the number of $B$'s. Commented Jun 27, 2014 at 13:14