Out of four questions, the hardest question for me was the question number one; Let L = {x in {0, 1}* | fourth-last symbol in x is 0 }. Prove that any DFSA that accepts L has at least 16 states. My first intuition of this question was really simple. There should be 8 states where the state accepts the claim because the fourth-last digit is always 0 but the first-last, second-last and third-last digit has to be different. Also, 8 states where the state rejects the claim due to the same reason. However, explaining my intuition did now follow the proper statements. My intuition does not even have a claim. Also, my intuition only explains the case where the number of state is 16. It does not explain further or lower cases. Therefore, I decided to use the proof by contradiction. I assume that the number of states can be lower than 16. Then at least two states from either rejecting state or accepting state have to be the same state. Then later states should be the same. If i can prove that the later sequences are different, I can prove that the claim is incorrect. Therefore, the number of states has to be greater than 16.
The rest of the questions were straight forward.I just needed to review the lecture slides and that was enough to prove the rest.
One thing I realized from this assignment was that the number of pages I used to prove these questions. For assignment one and two, I did not use more than a few pages for each question. However, for this assignment three, I spent more than three pages to prove a single question. I think this is like a metaphor of CSC263 that it will take a lot longer to prove a single question.
No comments:
Post a Comment