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.