The last quiz

 I did really bad for the last quiz today, tried so hard to figure out how to devise a DFSA that accepts strings with length which has a reminder of 2 if divided by 3.
 The question gives examples like 2, 5, 8, I can come up with 11 and so on, so a string is accepted as long as it's 3 units longer than the previous one. And empty string is clearly not accepted, in this case, the starting state can not be an accepting state, then whichever way to get to the accepting state needs at least two states, one of which is the accepting state. I just figured out I'm still don't fully understand what a DFSA is (I thought I understand it before this quiz, just a reminder, the key idea of DFSA is : every single state has exactly one transition for each possible input)
  So my actual solution is quiet simple like this:

  In this case, it totally works, and the RegEx for this DFSA is : (1+0)^2((1+0)^3)^* , I was so stupid during the quiz cuz I thought the question might be like devise a DFSA that accepts odd 0s and even 1s, which is similar to the tutorial question(Since this is how the previous quizzes work)
  Anyway, this quiz reminds me that I need to go through all those basic concepts during reviews.

Assignment 3

  Just finished the assignment for another course, now I finally got some time.
  For assignment 3, I'm not that confident with my work, but anyway, q1 took me quiet a lot of time to understand what I'm supposed to do, I figured it out by writing down states that satisfy the expressions and trace them by adding 0 and 1 then I found that they would go to different states at some point which is against the definition of DFSA, so if two strings start in the same state, then adding 0 or 1 to them should drive them to the same state again, otherwise, it would be a NFSA, so I get this contradiction.
   q2 is kinda like the examples used in lecture, all we need is a loop invariant, which is, the value of x and y are strictly decreasing throughout the loop, as long as x and y are natural numbers, then y is always going to hit 0 which means the loop terminates.
   q3 is something I saw in text book, just design a DFSA and then prove it by induction, need to point out the starting state and accepting state, as q1, I can get the idea that this DFSA need at least 3 states (since the starting state and accepting state can be the same).
   q4 confused me a little, the hint wants me to use the approach from lecture notes, but the one in lecture was written recursively, now I have to use a loop, I wrote 3 versions of the design in python, and the runtime of divide-and-conquer solution is indeed fast, the important thing to notice is that the algorithm should return the highest index of the specified value, which means if there's some duplicated values in the list, then the index of the last occurrence of that value should be returned, for divide-and-conquer algorithm, the most important thing is the max and min index, cuz we need them to calculate the middle value, so the loop invariant should be something like, max > min. Then it's just like q2, use induction to prove the loop terminates.