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.