Week 13 - LAST WEEK!

Wow time does fly by fast, 13 weeks passed by like the blink of an eye. This week, we had our very last midterm test. The first question on DFSA took me quiet a while to figure out due to the typos of the question, and also because I kept on making stupid careless mistakes when transiting between the states, which resultted in a different answer every time. Overall, I found the test was relatively easy.

I also took a look at the sample solution of assignment 3, if nothing major came up, I think I should've got a pretty good mark on it! ^_^

In the past 13 weeks, I sure learned alot. I really enjoyed this lecture with Danny, and I truely hope I can have him again as my prof for the coming courses~

Wish me luck for the exams~ =)

Week 12 - Non-regular Languages, Pumping Lemma

After spending weeks on the topic of regular expressions, now it's time to shift our interest to non-regular expressions. In order for a language to be regular, when the DFSA runs out of state, it has to repeat some of them, which is what pumping lemma was all about. Any language that can be shown to lack this "pumping" property is not regular, and to prove this, we use prove by contradiction. I haven't had a chance yet to pratice any of these non-regular expression questions, so I'll focus on this topic when I study for the final exam.


ASSIGNMENT #3

This assignment was okay overall. After spliting the questions with a partner, the work load was not too heavy at all. I went to the TA for help on one of the questions, and it didn't take me long to figure out the solution after given a hint. I am hoping to - and I really need to - get a good mark for this assignment. Other than that, I just need to remember to go through the questions my partner did, so I understand those concepts as well.

Week 11 - NFSAs, equivalence

Proving a design of DFSA is easy to do when breaking down to different cases and using induction. NFSA is more complicated than DFSA in the fact that each transition can take the machine to a set of states, rather than a unique state. So at least one of the states the automation could be in after processing x is an accepting state. For every regular expression, there's an equivalent NFSA, and for every NFSA, there's an equivalent DFSA, so this shows how the machine accepts complement, reversal, and intersection. The cartesian product gives an easier and directer approach for finding the intersection. There is an FSA for every regular expression, and we can also go the other say: there is a regular expression for every FSA. I still have not completely understood the concept of FSA, I will look into this topic further...


PROBLEM SET #6

This problem set took me longer to figure out than usual. The lecture example was quiet similar to this problem, but it wasn't clear to me at the beginning how I can apply the same concept to this problem... Now after I handed in my paper, I realized I only proved one way of the equation and forgot to prove the other way. Sigh, I guess I was over excited after I figured out the solution to half the problem and thought I was done.