This exercise comes from Introduction to Automata Theory, Languages, and Computation, Second Edition, by Hopcroft, Motwani and Ullman.

Exercise Description

In Fig. 1 (see below) is a marble-rolling toy. A marble is dropped at A or B. Levers x1, x2, and x3 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.

1. 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.
2. Informally describe the language of the automaton.
3. Suppose that instead the levers switched before allowing the marble to pass. How would your answers to parts 1. and 2. change?

Solution

1)

The finite automaton modelling the problem is defined by:

The alphabet is:

We identify 16 possible states in the problem: the 8 possible combinations of the levers combined with a previous situation of acceptance (the last dropped marble reached D).

Lets code the states using sequences of L (the level face to the left) and R (the level face to the right) followed with a final d if the last marble reached the D hole.

Then we have the following transition table defining the transition function :

Note that only 13 of the 16 states are reachable.

The initial state is and the set of final states is:

2)

The language of the automaton is composed by all the strings for which the extended transition function return a final state.

Lets see some examples of valid strings for the language:

• A
• B
• AA
• AB
• BA
• BB*
• AAA*
• AAB*
• ABA*
• ABB*
• BAA*
• BAB*
• BBA
• BBB*
• AAAA
• AAAB
• AABA
• AABB*
• ABAA
• ABAB*
• ABBA*
• ABBB*
• BAAA
• BAAB