Weeks 11-12: NFSAs/Pumping Lemma + Non-regular Language

Again, I'm writing a blog for 2 weeks, which is pretty bad as of the blog requirement. I will definitely write one for the last week of class! Looking back to week 11, we dealt with a lot of problems of NFSA and the new concept of the Cartesian product that was used in dealing with one of the problems for A3. There was indeed some confusion and difficulty when combining the two machines, binary string of odd length and multiples of 5 into one huge machine. If I remember correctly, I had about 16-18 states to list out. But the lecture material really did help in clearing up how to write up the Cartesian product of the delta function, accepting and starting states. Danny also went through a few examples showing how there is a regular expression for every FSA. However, I run into problems of choosing which state to remove first when trying to express the FSA to a regular expression.

We started off week 12 looking into the pumping lemma and proving it. Unforunately, the projector burned out again during lecture and everything was done on board. We were also introduced to grammars that contained productions and states denoting a language. Perhaps more examples can be found in the textbook. If possible, it would be great to see lectures posted from the evening class for revision of the test on Friday.