A marble-rolling toy In Fig- 2.8 is a marble-rolling toy. A marble is dropped at

Question

A marble-rolling toy In Fig- 2.8 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 marble will take the opposite branch. Model this toy by a finite automaton. Let the inputs A and B represent the input into which the marble is dropped. Let acceptance correspond to the marble exiting at D; nonacceptance represents a marble exiting at C. Informally describe the language of the automaton. Suppose that instead the levers switched before allowing the marble to pass. How would your answers to parts (a) and (b) change?

Explanation / Answer

>The inputs and outputs (A-D) become the alphabet of the automaton, while the levers indicate the possible states.
>If we define the initial status of each lever to be a 0, then if the levers change direction they are in state 1.
>Let’s use the format x1x2x3 to indicate a state. The initial state is 000.
>If we drop a marble down B, then the state becomes to 011 and the marble exits at C.
>Since we have three levers that can take on binary values, we have 8 possible states for levers, 000 to 111.
>Further identify the states by appending an “a” for acceptance, or “r” for rejection.
>This leads to a total of 16 possible states. All we need to do is start from the initial state and draw out the new states we are led to as we get inputs from A or B.

M = ({A,B,C,D,E,F,G,H,I,J,K,L}, {0,1}, delta, {A}, {A,B,I,J,K,L})
delta(A,0) = E delta(A,1) = D
delta(B,0) = F delta(B,1) = A
delta(C,0) = G delta(C,1) = B
delta(D,0) = H delta(D,1) = I
delta(E,0) = C delta(E,1) = H
delta(F,0) = D delta(F,1) = J
delta(G,0) = A delta(G,1) = K
delta(H,0) = B delta(H,1) = L
delta(I,0) = G delta(I,1) = B
delta(J,0) = C delta(J,1) = H
delta(K,0) = D delta(K,1) = J
delta(L,0) = A delta(L,1) = K

Key: State A corresponds to lever x,y,z positions ///
Key: State B corresponds to lever x,y,z positions //
Key: State C corresponds to lever x,y,z positions //
Key: State D corresponds to lever x,y,z positions /\
Key: State E corresponds to lever x,y,z positions //
Key: State F corresponds to lever x,y,z positions /
Key: State G corresponds to lever x,y,z positions \/
Key: State H corresponds to lever x,y,z positions \
Key: State I corresponds to lever x,y,z positions //
Key: State J corresponds to lever x,y,z positions //
Key: State K corresponds to lever x,y,z positions /
Key: State L corresponds to lever x,y,z positions //

>Two possible descriptions are
All strings ending in a 1, where the number of 1s is even.
All strings of length X that either end in a 1 or have an even number of 0s where X mod 4 = 0, or (X-3) mod 4 = 0 (X = 3, 4, 7, 8, 11, 12, ...).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.