Problem "Marble Toy"

Consider the toy shown below. A marble is dropped in at A or B. Levers x, y, and z cause the marble to fall either to the left or right. Whenever a marble encounters a lever, it causes the lever to change state, so that the next marble to encounter the lever will take the opposite branch.

                  |A|          |B|
                  |    |       |    |
                  | x |       | y |
                 /  /  \      /  /  \
                /       \    /       \
               /   /\    \  /    /\   \
              /   /  \    \/    /  \   \
             /   /    \  z /   /    \   \
             \   \    /   /    \    /   /
              \   \  /    /\    \  /   /
               \   \/    /  \    \/   /
                \       /    \       /
                 \     /      \     /
                  |   |        |   |
                  |   |        |   |
                   |C|        |D|


Problem: Describe the set accepted by the DFA. Solution:


First the DFA solution is presented in the next table and his diagram in JFLAP in the next file.

To describe the set accepted by the DFA see that only the half of times that a ball falls in A affects x_2, the same happens for the case B. Then there are three cases to describe the set accepted by the DFA.

1.-If the word end in B and the numbers of Bs is even (par).
2.-If the word has the form XB where X is formed by As and Bs. The number of Bs on X is even and the half of the numbers of As and Bs is odd (impar) (exactly).
3.-If the word has the form XA where X is formed by As and Bs. The number of As on X is odd and the half of the numbers of As and Bs is odd.(exactly).