Problem Solving Question.

Piles of pennies

You are sitting in front of two drawers. The left drawer contains 64 pennies, the right drawer contains nothing. Can you arrange things so that one of the drawers has 48 pennies, using the following two operations:

L: If the left pile has an even number of pennies, transfer half of them to the right pile. If the left pile has an odd number of pennies, operation L is disallowed.
R: If the right pile has an even number of pannies, transfer half of them to the left pile. If the right pile has an odd number of pennies, operation R is disallowed.

What about arranging things so that one of the piles has other numbers in the range [0,64]? What about starting with a different number of pennies in the left drawer?

****************************************

Step 1: Understand the problem.
This question need us to figure out the way to rearrange the pennies in the two sets by only apply two operations namely, L and R. The operation of L and R are identically the same, only difference is they only implement the operation in each specific set.

Some observation as follow:
(0). The initial states requires the left basket only can contain even number of pennies, otherwise there will be no operation for the problem.
(1). We can only use the L or R operation if any set contains even number of pennies. Otherwise the L or R and be implemented.
(2). If one of the set contains odd number of pennies, we can't have further operation until we move odd number of pennies into this set from the other one.
(3). Following the last step, if odd number of pennies moved in, then other set moved from will end up with odd pennies. This means we can't have any further operation for moving from set .

Step 2: Devising a plan.
(1). Observe the first few cases to see if any pattern can be concluded for this problem.
(2). Try to give a formula to instruction about the operation rules.
(3). Try to generalize the case with different start case.

Step 3: Carry out the plan.

Q1: left drawer contains 64 pennies, end with one of the drawers has 48 pennies
(0). 64|0 # initial case
(1). 32|32 # move half(32) from left to right
(2). 48|16 # move half(16) from right to left
Then at the end of the two operations we end up with 48 pennies in one of the drawers as required.

Q2: one of the piles has other numbers in the range [0,64]
(0). We can easily see that we can't generate a none penny pile in our system. Since zero times two is still zero, that's means we can't divided a pile by half inorder to generate a zero.
(1). Since we can't generate zero, how about 1? The answer is yes, since in this algorithm 64 is a power of 2 number, the only thing we need to do is to divided the same pile by many times. then we can easy to get a 2, and then once again, we can get 1.
(2). Actually we can generate any number by provide the initial value of 64 or any powered 2 natural numbers. The proof can be done by using recursive loop.

Q3: What about starting with a different number of pennies in the left drawer?
(0). As mentioned above the left drawer can't start at a odd number, otherwise there will be no more operation.
(1). Any number that powered by 2 is a good starting number, this means we can generate any number other then 0.

Step 4: Looking back.
This question is an open question, there can be a lot of questions related to this question, by simply change the starting value in the left drawer or by give an different operation rules.

S->S means empty

In this weeks lecture danny talked about the context free grammars. 

When danny ask a question about what the grammar S->S, stands for?

My first instinct is if s always return s itself, then s can't be anything that related to repetition which we are frequently used in the regular express, we called it Kleene star. Since Kleene star is out of the consideration, i made a conclusion that S->S represent a finite string.

However, danny said it represent empty. 

I think about it after class, found danny is right.

Here is the thing, since we start at S, and our destination is always S, the trick is S is start point and also a destination point. Thus, that's means you always stay at where you are. Thus, the S->S means empty. 

It may sounds confused by how about S is /epsilon (empty string), actually, in the lecture for FSA, we use /epsilon  to direct start state to another states, if S->S is /epsilon then is contradict with S->S where the destination state S is itself, it doesn't direct to any state other than itself. Thus S->S only should be empty.

Another way to think about this question is there is no other output, i.e. S-> B. Thus if any CFG that doesn't include a end point other than itself, this CFG either never ends or just empty. 

S->S means empty

Pumping Lemma

Found an interesting article about pumping lemma, it is a poetry about pumping lemma. Here it is.

The Pumping Lemma, in poetic form

“Any regular language L has a magic number p

And any long-enough word in L has the following property:

Amongst its first p symbols is a segment you can find

Whose repetition or omission leaves x amongst its kind.”

“So if you find a language L which fails this acid test,

And some long word you pump becomes distinct from all the rest,

By contradiction you have shown that language L is not

A regular guy, resiliant to the damage you have wrought.”

“But if, upon the other hand,x stays within its L ,

Then either L is regular, or else you chose not well.

For w is xyz, and cannot be null,

And y must come before p symbols have been read in full.”

“As mathematical postscript, an addendum to the wise:

The basic proof we outlined here does certainly generalize.

So there is a pumping lemma for all languages context-free,

Although we do not have the same for those that are r.e.”

By Martin Cohn and Harry Mairson

Regular Expression

Many of us have written applications where we have used regular expression for different tasks, like validation , parsing and other related task. Like the a1 of 207, we have the regular expression to read the user's input of next move. After learn regular expression in csc236 i can understand how those code works. Regular Experssion is quite a powerful tool, and has been available in most of the programming languages. I believe, most of the time, like us, use this tool is to search specific words in a long paragraph.

In csc236, seems we talk about the regular expression, we only focus on binary string which contains only 0 and 1. The more interesting about regular expression is to deal with words that other than bianry string. Like the pattern contains words and numbers, or even the charater witht the back slash.

Usually in a regular expression ‘\’ is used as a the escape sequence , to escape meta characters. Regular Expression also support a construct called ‘character classes’ ,which can be roughly taken as a set of characters. There are some pre-defined character classes like \d \w \s etc. and if you need a more customized version you can define your own using Square brackets notation "[]" with represent a set that match the pattern inside.

The world inside the square brackets is much different than the one outside.  Inside the brackets , there are only two meta characters, ‘^’ and ‘-’; even an opening bracket ‘[', asterisk '*' , plus sign '+' are not considered as meta inside []. Furthermore , [] has no escape sequence within them. Now what you will do if you want to have ‘^’ , ‘-’  and ‘]’ inside a character class.

Even Zeros and Odd Ones

This question left in today's lecture is interesting, said need to find a regular expression by using the set (0,1) to produce even zeros and odd ones. The graph which is drawn in the lectur can slove this question easy. Image there is four staes say s0, top left, s1, top right, s2, bottom left, s3 bottom right. Obvious we know that:
s0 and s1 represent even ones, while s2 and s3 represents odd ones.
s0 and s2 represent even zeros, while s1 and s3 represents odd zeros.
Here our question becomes the way that travesal from s0 to s2 where is our destination that represented by even zeros and odd ones.
After all the setup above, we can start our travesal. One thing need to point out is there are many self-circle(?what is the official name for this?) should be considered, like s0 to s1 then back to s0.
Ok, here we go. Start from s0.
1. We can directly go from s0 to s2 where is our destination, done! Easy case, may called base case??
2. From s0 to s1 to s3 to s2, which is the clcokwise traversal. Thus we can get the expression like 010. However, we can have s0 to s2, not stop here, but go to s3 and then back to s2. There are many cases need to consider, keep in mind that s3 can go back and forth with s1 and s2 many times. Likely wise, we can have a countclockwise traversal, from s0 to s2, it is a duplicate expression from where we discussed above. Thus we can conclude that 1+(01+10)(11+00)*0 is our expression.
3. The above expression just from s0 to s2, we know that there are a lot of ways from s0 to anywhere states and come back to s0 again, this situation should concatenate with the expression above. From s0 to s1 back to s0 will gives us 00, so to s2 back to s1 will gives us 11. More states now s0 to s1 to s3 back to s1 will give us (01+10)(00+11)*(10+01), so or then up and concatenate with first expression gives us.
(00+11+(01+10)(00+11)*(10+01))*(1+(01+10)(11+00)*+0)