Last Day of Class

Finally! We reach the end of semester.
During this course, I leaned a lot knowledge of application of logic and proof techniques to computer science. Also mathematical inductions, correctness proofs for iterative and recursive algorithms, recurrence equations and their solutions, such as using The Master Theorem, and introduction to automata and formal language.
Wish everyone gets a great grade on final exam and I will continue working hard for final exam which is weighted for 35% of the course. Pretty high, right? =p.

And merry christmas to all!

First question in assignment3

I spent more time on the first question than the other three. I came up with no ideas at the beginning, and I logged in to piazza to seek some hints. And I found that the professor introduced a way of thinking for us to prove contradiction. Then I followed the track and came up with my solution as following. I may not get it perfectly correct. This is just what I believe one way to solve it.

The question is as following:

Let L = {x belongs to {0,1}* | fourth last bit in x is 0}. Prove that any DFSA that accepts L has at least 16 states.

And my proof is:

Claim: Let L = {x ∈ {0, 1}* | forth-last symbol in x is 0}. Any DFSA that accepts L has at least 16 states.

Proof: We use proof by contradiction to prove the above claim on L.Assume there is a DFSA accepts L has less than 16 states. Since there are 16 different combinations of the last four bits of the string, in other words , then at least two of the 16 states can be reduced to one. Let x and y be two different arbitrary states from the 16 states. We must show that this leads to a contradiction. There are four cases.

Case 1: The fourth last symbol in x and y are different.
In this case, one of the two states should be accepted by the DFSA and
the other one should be rejected. Then they cannot be reduced to the same state.

Case 2: The third last symbol in x and y are different.
In this case, if we append k ∈ {0,1} to both x and y, then the third last symbol now becomes the forth last. Because the third last symbol in x and y are different, then the fourth last symbol after appending k of x and y are different. Then, one of them should be accepted by the DFSA while the other one should be rejected. Then they cannot be reduced to the same state.

Case 3: The second last symbol in x and y are different.
In this case, if we append k ∈ {0,1}2 in both x and y, then the second last symbol now becomes the forth last. Because the second last symbol in x and y are different, then the fourth last symbol after appending k are different. Then, one of them should be accepted by DFSA, and one should be rejected. Then they cannot be reduced to the same state.

Case 4: The last symbol in x and y are different.
In this case, if we append k ∈ {0,1}3 in both x and y, then the last
symbol now becomes the forth last. Because the last symbol in x and y are different, then the fourth last symbol after appending k are different. Then, one of them should be accepted by DFSA, and one should be rejected. Then they cannot be reduced to the same state.

Since no states in the 16 possible states can be reduced to one in all four possible cases as all four of them lead to a contradiction.
Hence, we get the conclusion that any DFSA that accepts L has at least 16 states.