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 X1 and X3 to the right. If the gates are configured as X1 and X2 to the right, and X3, X4, and X5 to the left, then dropping a marble down chute A results in the marble exiting chute D and toggling gates X1 to the left and X4 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 X1X2X3X4X5).
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
Reviews
There are no reviews yet.