Proof by contradiction

In this post I will continue talking about question 1 of assignment 3, recording my proof.

I had a DFSA with exactly 16 states that accepts language L and noticed that it drives each binary string of length 4 to a different state. From there, though, I had no idea how to prove that any DFSA that accepts this language must have at least 16 states. I had not seen something similar to this before. Finite state machines did make sense to me during the lectures, but I had not had enough practice with them yet. Also, almost immediately I realized that this proof can not be done using induction - or at least I did not see a way of doing it. That meant that it was going to be different than most of the proofs that I got used to writing in this course.

I remembered my math teacher in high school. He would always remind me that when I am stuck on something and can not prove it, I should try proving instead that it does NOT hold. Indeed I was completely stuck this time and did not know how to start.  That is how I thought of proof by contradiction.
Also, my intuition kept telling me that the fact that the machine is deterministic would play an important role in this proof. It was definitely something I had to use.

I then looked at my DFSA. I noticed that if a string started with 0, for example and was of length 4, it would end up in one of the leaves of the binary tree. If I add one more bit to that, in some cases it would be still be accepting while in some others it would not. I kept adding random bits to it to see what happens. I noticed that it was always the case that when a string of length 4 had 0 as the third-last bit, then if I add 1 random bit to it, it will end up in an accepting state for sure, since the 3rd last bit has now become the 4th last bit. If I add another random bit to it, it will go to an accepting state if and only if the 2nd last bit of the original string was a 0. That observation turned out to be the key in proving this, for the following reason:
If we take two different binary strings, then they will surely have at least 1 different bit. Now if that 1 different bit is not the fourth-last, for all we know they could indeed end up in the same state (since they will either both be accepting or non accepting). However, by adding the right number of random bits to both, we can make it so that the fourth-last bit of the strings we are constructing is different. Then, if we further assume that we are adding the same bits to both strings every time, we have our contradiction. The reason that this is a contradiction is that the machine will eventually drive the two strings we constructed to two different states (since at the point where we have added enough bits and the fourth-last bits of the two strings are different, one will be accepted while the other will not be) under the assumption that they started off at the same state and that we kept adding the same bits to both. From this, it follows that the machine is not deterministic. But this contradicts our hypothesis.

So I now had the basic idea of my proof, and the only thing left to do was to properly structure it and write my thoughts down in a way that any reader could be convinced that I proved what needed to be proved.

I observed that the maximum number of times that one would have to add random bits to the two strings is 3. This is because, if the fourth-last bits are different, the contradiction follows immediately. If they are the same, then there is the case where the third-last bits are different. If they are, then adding 1 bit to both strings would be enough to show the contradiction. If, however, the third-last bits are the same, then we must consider the case of the second-last bits being different, in which case we would have to add 2 bits to each string to end up with a contradiction. Finally, if the second-last bits of the two strings are the same as well, then it has to be the case that the last-bits are different, since we started with two distinct strings. In this final case, we would have to add 3 bits to each strings to show the contradiction.

At this point, it was clear to me how my proof would be structured. At first, I would assume that there exists a DFSA with less than 16 states. From that, though, it follows that some binary strings of length 4 would have to end up in the same state, since there are 16 of those but at most 15 states in the machine. Then, considering I would consider 2 cases, in the first of which the contradiction would be obvious, since the fourth-last bits of the strings are different and in the second of which I would have to add some number of random bits to the strings in order to end up in the contradiction. That second case would have three subcases, depending on the number of time that I would have to add a random bit to the strings (first case: third-last bits are different, add a bit to each just once, second case: second-last bits are different, add a bit to each two times, third case: last bits are different, add a bit to each string 3 times).

Now reading it through again, it makes total sense to me why any DFSA that accepts L must have at least 16 states. I believe that every step of the proof follows from the previous ones and it all builds up to form a contradiction in each subcase of each case, which proves the desired result.