Lucy and Charlie are sitting at a table. On the table is a square tray with four glasses at the corners. Charlie's goal is to turn all the glasses either right-side up or upside down. However, Charlie is blindfolded and he is wearing mittens. He does not know the initial state of the glasses. If they are initially all turned the same way, then Charlie automatically wins. In his turn, Charlie may grab one or two glasses and turn them over; however, because of the blindfold and the mittens he cannot see or feel whether the glasses he grabbed are right-side up or upside down. He can, however, choose whether to grab adjacent glasses or diagonally opposite glasses (or just one glass). If the glasses are all turned the same direction, Lucy announces that Charlie has won. Otherwise, Lucy may rotate the tray, just to make Charlie's goal harder. Find the shortest sequence of actions by Charlie that is guaranteed to win the game, no matter how Lucy plays. Prove that your solution is correct and is the shortest possible. First solve the problem with an all-NFA. Then covert it to a DFA that is equivalent. Then write down your answer, with the proof of correctness and optimality.

Hint:

Because Charlie cannot tell if a glass is rightside up or upside down, and Lucy can rotate the tray arbitrarily without Charlie knowing, the following states are sufficient for the All-NFA that you create:

1) All glasses rightside up, or all glass upside down.

2) One glass rightside up (and the others upside down), or one glass upside down (and the others rightside up)

3) Two adjacent glasses rightside up, and the other two upside down.

4) Two diagonally opposite glasses rightside up, and the other two upside down.