week 11 -- a3

Well, after just having finished a3 (literally), I'm feeling good about regular expressions and finite state automata. I didn't find any of the material too difficult and found the assignment (fairly) straightforward. Most of the definitions and proofs in regular expression are defined using structural induction, which I feel that I am already familiar with.

Question 4 on the assignment did pose me a bit of trouble. I initially took the approach of analyzing entire strings that were multiples of 5, trying to find a pattern, which I felt would help me nail down which states a corresponding machine might take. In going to TA office hours, I found out that this was the wrong approach. I found it was better to look at each individual symbol as it was being inputted into the machine, where a 0 would multiply that number by 2 and a 1 would multiply that number by 2 and then add 1. To find the machine I then just looked at the last digit (in base 10) and made 10 states accordingly.