[Solved] p2 CS373

Construct a DFA using JFLAP that simulates the following game (modified problem 2.3 from Hopcroft/Ullman). We drop a marble down the chute labeled A or B. If the last marble that we drop down the chutes comes out one of the chutes labeled C or F, then we loose. If the last marble that we drop down the chutes comes out one of the chutes labeled D or E, then we win.

To simulate this we have an input alphabet of {0, 1}. An input symbol of 0 simulates dropping a marble down chute A and an input symbol of 1 simulates dropping a marble down chute B. Each time a marble touches a gate it toggles the gate to the other direction and the marble goes in the direction that the gate was set to prior to being toggled. Initially all of the gates are configured to the left (as shown in the diagram). As an example, if all of the gates are positioned to the left, then dropping a marble down chute A results in the marble exiting gate C and toggling gates X₁ and X₃ to the right. If the gates are configured as X₁ and X₂ to the right, and X₃, X₄, and X₅ to the left, then dropping a marble down chute A results in the marble exiting chute D and toggling gates X₁ to the left and X₄ to the right.

You are to construct a DFA using JFLAP that simulates this marble game, with the DFA accepting those strings that result in winning and rejecting those strings that result in loosing.

The DFA is quite simple to understand, but is tedious to construct, since there are potentially 64 states (32 non accept states and 32 accept states).

Trace of configurations for various inputs (values for X₁X₂X₃X₄X₅).

1111

LLLLL->LRLRL->LLLRR->LRLLR->LLLLL

0000

LLLLL->RLRLL->LLRRL->RLLRL->LLLLL

10101010

LLLLL->LRLRL->RRRRL->RLRRR->LLRLR->LRRRR->RRLRR->RLLRL->LLLLL

01010101

LLLLL->RLRLL->RRRRL->LRRLL->LLRLR->RLLLR->RRLRR->LRLLR->LLLLL

Sample strings (half accepted and half rejected)

1111111110

0111001100

0001011010

0110100110

1000001010

1001011101

0011101011

0101000101

1100010001

1010011101

Six of my test strings (half accepted and half rejected).

0111111000101010010110101011110011100010110010100100110010110111010000101000001010010111110110011010

1000000010101000011100101101101100011110010001101111001110011110011110101011010011001001011010011010

1010001011000001111011101010010110111111100110010101110110110100100010011101111111010101011100010110

1111100001001111111101110100100010011010010011000010100001011000001100101000000010101010001111100100

1111110001101111011111001110001110110101110011001111101100001010110101000101100011011111001100001110

01100001001110000111011101000100011011001111110001000000101111000100001111101110111011011010100010002