Polya Problem

Test 3, question 1.

The question described the machine that accepts odd length strings with a number of 1's that is 2 mod 3 (when divided by three has a remainder of 2). The first part of the question asked us to define, without proof, the state invariants and the second part asked us to give the state of the machine for a given extended transition function.

Step 1, understanding the problem:
The first part of the question asked us to define the states of the machine. For this part of the question I needed to understand the individual machines whose intersection formed the machine in the question. I then needed to find the Cartesian product of the two machines to get their intersection. Finally I needed to understand the transition functions of each machine, specifically which state they went to after seeing a certain input at a certain state. With these I thought I could describe the state transitions for the first part of the question and then use these to solve the second part of the question.

Step 2, devising a plan:
Since I had seen a similar problem on the third assignment, the machine that accepts odd length strings divisible by 5, I initially decided to approach the problem in a similar manner. Since the problem gave the transition of each state on a given input, I decided to use the one state invariant the question had given us to figure out the other 5. Once I had gotten the state invariants, I could use this information to determine the state of the machine for a given extended transition function for the second part of the question.

Step 3, implementing the plan:
I started by drawing out the individual machines. The machine for accepting odd length strings was simple enough, it had two states with a starting state for even length strings that transitioned on a 1 or a 0 to the accepting odd length string state and that transitioned back on a 1 or 0 to the even length state. The machine that accepts strings with a number of 1's that is 2 mod 3, was more complicated but the concept was similar. The question gave us the state invariant that was (q0, q'0)=an even number of zero's and a number of 1's such that 0 mod 3, using the two machines and this invariant I found that the other invariants were:
(q0, q'1)=an even number of zero's and a number of 1's such that 1 mod 3,
(q0, q'2)=an even number of zero's and a number of 1's such that 2 mod 3,
(q1, q'0)=an odd number of zero's and a number of 1's such that 0 mod 3,
(q1, q'1)=an odd number of zero's and a number of 1's such that 1 mod 3,
(q1, q'2)=an odd number of zero's and a number of 1's such that 2 mod 3,

For the second part of the question, I used the previous states to determine the state the extended transition would lead to. For example the state
d*(S,100100) has an even number of 0's and 2 1's, which when divided by 3 has remainder 2. Thus it is in state q0,q'2.

Conclusion: Overall I found that I was able to effectively apply my past experiences from assignment 3 to help me with this question. I was satisfied with the way I solved this problem and I think my method was the most efficient way to approach the problem.