week 11 - NFSAs, Equivalence

Finally after reading through the notes for DFSA, I've figured out the how the DFSA works and i've also finally understood the example about strings that are multiples of 3 in base 2. Sounds complicated, but actually it's quite easy. But to design a DFSA will require careful thought to ensure nothing is left out.

This week we did NFSAs and equivalence. Proving the DFSA sounds straightforward. Just start with the base case that all portions of the state invariant are true, then go on to use x=x'a, a concatenation of strings, to show that the property is preserved. Structural induction in this case? We have to show that starting from a smaller substring x', we arrive at the same state invariants for x as well.

As for NFSA, i have to read up on that. All that NFSA set of states vs DfSA sets is confusing me. We also did cartesian product. It's like a pair of DFSAs to be combined in to one. It's not all that bad.

BUT for regular expressions, the example for even #of 0s and odd # of digits was not all that clear. After removing q_11, why did the transitions linking q_00 to q_01 and q_01 to q_00 change from 1 to 1+01(11)*10? Since q_11 was only linked to q_00 and q_01, why did the transitions from q_00 to q_01 get affected when it was removed?