We started with a proof that was owed from the week before. Professor Heap proved the correctness of the DFSA we saw last week (accepting binary strings that are multiples of three). The proof used structural induction on string x.
We continued the lecture with NFSAs. We saw that every regular expression has an FSA (if we allow empty transitions) and that every NFSA defines a DFSA.
We also looked at the cartesian product method (if you paid attention to that then Problem # 4 on Assignment # 3 was easy to do).
Assignment # 3, the last assignment for this course was due Monay, Nov 24 (so it was due yesterday as I am posting this on Tuesday, Nov 25). I found this HW the easiest of the three. The hardest problem for me was Problem # 2, where we had several regular expressions and we had to prove whether or not the regular expressions denoted a language L (L was the set of all binary strings with an even number of 1s). Most of the times I can see if a regex denotes a language with a certain property but I have a hard time proving it. I guess that's always the case. I am getting better though because Problem Set # 6 dealt with this thing and Problem # 2 of Assignment # 2 and we saw an example of this in class. Practice makes perfect.
Subscribe to:
Post Comments (Atom)
2 comments:
Yeah - how exactly were we supposed to do the proofs for question 2. I hope it's right though, and not too little too late.
..lyke omg rofl rofl obv!
My term paper for my Language class is on language and the internet. I was with you up until the last abbreviation, obv. What does it stand for?
Post a Comment