1
$\begingroup$

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.

enter image description here

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

enter image description here

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 \?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Jun 4, 2014 at 15:49
  • $\begingroup$ @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$. $\endgroup$
    – Rick Decker
    Commented Jun 4, 2014 at 20:29

1 Answer 1

Reset to default
3
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – juaninf
    Commented Jun 24, 2014 at 7:24
  • 1
    $\begingroup$ The position of $x_2$ depends on both the number of $A$'s and the number of $B$'s. $\endgroup$
    – Hendrik Jan
    Commented Jun 27, 2014 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.