Question 1 A Rubik’s Cube is a puzzle in the shape of a cube. Each face is covered by nine stickers, each of which is coloured with one of six colours: white, red, blue, orange, green, andyellow. An internal mechanism enables each face to turn independently, thus mixing up the colours. For the puzzle to be solved one has to manipulate the cube so that each face again consists of one colour. Pictures of a Rubik cube in its initial state, and one with the colours confused, are shown.
Let us consider a fixed position of the cube and we will then label the basic moves as follows: F (Front): rotate the side facing the solver through 90 degrees clockwise; B (Back): rotate the side opposite the front through 90 degrees clockwise; U (Up): rotate the side above the front side through 90 degrees clockwise; D (Down): rotate the side opposite the top side through 90 degrees clockwise; L (Left): rotate the side directly to the left of the front through 90 degrees clockwise; R (Right): rotate the side directly to the right of the front through 90 degrees clockwise. Consider the set S of all sequences of moves that start with the cube in its initial state (i.e. with each face consisting of a single colour) and which return the cube to that state. Show that S is a regular language over the alphabet {F,B,U,D,L,R}. (If your argument is based on a finite automaton accepting S then it is not necessary to construct the automaton explicitly but you should explain how such an automaton could be constructed.)
Hint: There are only finitely many states to the Rubik's cube (43,252,003,274,489,856,000, or about 43 quintillion, according to the Wikipedia page.) Base your finite state machine on those states.