(RUF)^5  swaps two corners, makes a mess of edges, but the other six corners are untouched.  If you know what you're doing and swap things in the right order, you can also control parity with this.

(R^2 U^2)^3 swaps two pairs of edges.  So doing this repeatedly, I can all the edges in the correct place, without messing up the corners.

(RUF)^40 leaves the corners untouched and the edges are in the same place, but it flips the orientation on certain edge pieces.  Doing this strategically enough times will solve the cube.

(R U^2)^????  But this would rotate one center 180 deg, leave everything else untouched.

The 90 degree needs were solved by the classic pattern


Consider the various legal configurations as a group.  Take a solved cube and do RU.  Take another solved cube and do UR.  The cubes don't look the same.  Therefore this group is not abelian.  Therefore it is not cyclic.

CONTEXT SENSITIVE GRAMMARS

A language is a set of strings over an alphabet.  A grammar is a set of rules.

Some have defined the Internet as:

The largest partition of the reflexive, symmetric, transitive closure of computers under the relation "can receive a message under the IP protocol from"

Consider the language {ww|w in Sigma*}, in other words the set of duplicated strings:  aa  catcat  molybdenummolybdenum.

CHOPKINS CaFe Mg B Mn CuZn Mo

Prove that this language is not Context-Free.

(Break string up into uvwxy.  |vx| >= 1 |vwx| <= k )

a^k b^k a^k b^k .

Since |vwx| <= k  Either

vwx = a^k   or b^k in which case pumping v and x would increase the number of letters in one half without changing the other half.

OR

vwx is some number of a's followed by some number of b's or the other way around.

If either v or x contain both a's and b's, then pumping it will add another ab or ba to one half of the string, but not the other.

If neither v nor x contain both a's and b's, then one is all a's and the other is all b's.  Pumping it gives us more a's than b's on one side and more b's and a's on the other.

aaaabbbbaaaabbbb

I don't know the grammar offhand, but {ww} is certainly a context-sensitive language because you can easily write a program to definitely determine whether a string is in that language.

This specific language essentially that most sane programming languages used by most sane people are not context-free.  There is no context-free way to tell if the second half of a string matches the first half.

By extension, if you declare and then use that variable, there is no context-free way to determine whether the variable you're using matches any of the variables you declared.

X<-X+1  vs.   X++

So compilers can't rely purely on CFG's to compile a program because CFG's are just not powerful to describe a programming language.

They also can't rely pure on CSG's to compile a program because CSG's are complicated and hard to understand.

So instead compilers use a grammar to describe most of the language, but certain features like parameter matching or variable use are simply omitted the grammar, but the grammar is supplemented with code to check for this stuff manually.

For Program 1:  this isn't too hard because your parser isn't that great.  This is based on the notion that the right side of production rules in a CFG are never shorter than the left-hand side.  For this assignment, we will assume that this is strictly true so the empty string will never be considered part of any language.

You will need a data structure called a queue.  The way to do this is to process it in reverse.  Start with the string you want to test and see if you can make it back to the start state.

Start with the input string and see if you can apply any of the rules (in reverse) to the string.  See if any substring matches anything on the right, if so then replace it with the left side of the rule and put it on the queue.  If you can make multiple replacements, only do one a t time and put each result onto the queue.  (If have two changes that I can make, make the first change, put it on the queue, unmake that change, make the second change and put that on the queue.)  So each thing you add to the queue differs by ONE production rule from the string you're working on.

When you're done, take the first item from the queue, and apply the same process to it.  Make replacements one at a time, applying productions in reverse, and add them to the queue.  Sometimes you won't be able to make replacements in which case, there's nothing to add to the queue.

Never add a string to the queue that has already been added to the queue.

Now, if you keep doing this, one of two things will eventually happen.  You'll get a string consisting only of a start symbol (which means you win, the string is in the language), or you will attempt to remove a string from an empty queue (which means you lose).

This sucks, but it works.  It works because in a CSG, the right side is never shorter than the left side.  So when your production rules in reverse, you are (generally speaking) replacing larger substrings with smaller ones so that your strings get shorter eventually becoming only one symbol long (S, ideally) or you run out of things to try.

Now, you can replace a string with a string of the same length, but this process can't go on forever either, since there are only a finite number of strings of that length, and you can't save the same one twice.

This will terminate:  you will end up with S  or an empty queue.

This is the difference between type 1 grammars (CSG)'s and unrestricted grammars (Type 0).  With unrestricted grammars, the right hand side can indeed be shorter than the left hand side, and so this process could conceivably go on forever.