Final Update

This is probably the last post in the slog. In this csc236 course slog I wrote 20 posts, average 1.5 post per week, including a problem solving question. Most of the posts are the thought about the course material. Unlike other classmates who gonna post mass posts right before due date, I keep writing slog in every single week. As I mentioned before in the 165 course slog, I think slog is a very good environment for us to review course material and share the thoughts. If anyone post large amount at one time, probability the posts will copied from somewhere else or just some crap words that make nonsense. So I keep writing post every single week. Need to mention that in the 165 slog I got A for my slog, I believe this csc236 slog will Aces as well.

I keep this slog default layout, white background and black fonts. Sometime when I get into others slog, someone try to make the background black or put really shinny color, honestly, I won't read those slog for more than 1 or 2 posts, coz, it is really not read friendly. So, I keep my slog simple and default the layout and color.

Tomorrow we will have a test and there is only a final left. I really appreciate Danny's effectively teaching for this course. My friends told me this course is really hard, I just want to say Danny really make this course easy for us to understand. Thank you Danny. I hope you can teach us for any other course later on.

OK, probability this is all I want to say for this slog. Thanks anyone that review and comment my slog.


Simon
Dec. 2008

PSA

The second topic today is about PSA, a updated version of FSA, that we are allowed to use a stack. This is the perfect case that we can use this stacked automate to solve some problems like Matching Parentheses or like the one we left after lecture, same number ones and zeros. I didn't get a chance to think this question deeply before I wrote this slog. I think I have some sort of clue that when we see a 0, we push 0 to the stack, when we see a 1, we pop a 0.

we need to have a start states and two states that paralleled to each other that accepting 1:/epsilon X and 0:/epsilon X respectively. Furthermore, we need to have another states that connecting with the two states mentioned above, realize that I should label them as S1 and S0, then they connected to the states S3 say... to be continued...

CFG to FSA

Coming later today's lecture, coz I had a math test before that. Fell weird that danny use the blackboard again. Today's lecture is about converting CFG to FSA. Topic is interesting, coz there are connection about the regular expression and FSA that we learned weeks ago. Again, now we are talking about the connection of CFG and FSA, which is more related each other than RE to FSA, personally speaking.

The method is straight forward, instead of having a long states and all the lines, we put each line from one state to another as an single context free grammar. There is works. Just remember that we need to have a right linear that some state to empty or any string preappend to a the terminal state.

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.