2
$\begingroup$

enter image description here

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.)

$\endgroup$
  • 1
    $\begingroup$ The question ask you "Show that S is a regular language over the alphabet". What is your question to us? You want some hint how to start, some references to look things up or what? $\endgroup$ – achille hui Aug 11 '14 at 13:05
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.