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.

Problem solving

The time has come to talk about problem solving. It is probably a weird time to talk about solving an exercise of the assignment after I have already submitted it, but I did not want to waste precious time writing this up while the clock was ticking before the deadline. Besides, I have a good memory and I can clearly remember the details of my thought process during those days. Actually, it would have been weird if I had forgotten those details, considering the time I spent on this question, the number of conversations I had with myself in my room, in the subway, while walking on campus etc.

I have chosen to talk about question 1, since it was the question of the assignment that I was stuck on for the most time probably and at the same time, the question I enjoyed the most.

This question is about proving that any DFSA that accepts L has at least 16 states, where L is the language of binary strings whose fourth-last bit is a 0.
I read the question many times and read the hint as well. I then wrote down the 16 binary string of length 4 and highlighted the ones that would be accepted by DFSA (the ones whose first bit is 0). In order for the DFSA to have at least 16 states, there must be some way to prove that each one of these 16 binary strings of length 4 would have to end up in a different state than the rest.  But I had no idea why that made sense and surely no idea how to prove it.

My next thought was to construct a DFSA that accepts this language, since maybe that would help me see why at least 16 states are needed. It took a surprisingly long time to come up with a working DFSA for this purpose. When I finally got it, I counted the states I had and they were exactly 16.
My DFSA looked like a binary tree. On the very top, was the starting state, with a self transition of 1s. This starting "node" had one child only, to which one could be lead to with a 0. That "node" of the DFSA (the child of the starting state) is the root of the binary tree. It has two children: one could get to the first one with a 0 and to the second one with a 1. Each of those children has another two children that can be reached in the same way and each one of those has another two children. Those final children are the "leaves" and each one of them is an accepting state of the DFSA. From the leaves, there are transitions back to the very top in some cases, or back to the root of the tree in other cases, or to the father of grandfather of the leaf in other cases, or even to other leaves sometimes.

I then tested my machine with the 16 binary strings of length 4 and indeed, each one ended up in a different state. Among those 16 binary strings of length 4, there are 8 strings that are accepted by L and 8 that are not accepted by L (since exactly half of them start with a 0 i.e. exactly have of them have 0 as their fourth-last bit). The ones that are accepted by L ended up in one of the leaves - there are exactly 8 leaves in the DFSA that I described above, one for each of those 8 accepted strings. The ones that are not accepted by L, on the other hand, never made it to the leaves, since the self transition in the starting state happened at least once and so there were at most 3 bits left after that, which are not enough to drive the DFSA to the leaves.

At this point, it made sense to me why each binary string would end up in a different state, but I still had no idea about how this can be proven.

In the following post, I will record my thought process that lead me to the proof.