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. 

DFSA and REGEX

I found the second tutorial question this week was a little bit challenging for me. After spending one day for it (i am not smart =p), I got the solution here.  I feel great after finally my got the answer.

The question is as following:
Let L be the set of strings over {0, 1}* that begin and end with the same bit. Devise a regular expression, R that denotes L, and prove that your regular expression is correct.

My answer is as following:

R = 0 + 1 + 1(0+1)*1 + 0(0+1)*0

Claim:
 L(R) = L => L(R) is subset of L ^ L is subset of L(R)

Proof:
Suppose s is an arbitrary string in L(R). Since L(R) is a union of 4 smaller languages, We consider 4 cases.

    case 1 and case 2    s belongs to L(0) or s belongs to L(1)
        Then either s = 0 or s = 1 begins and ends with the same bit 0 or 1 respectively.

    case 3 and case 4    s belongs to L(0(0+1)*0) or s belongs to L(1(0+1)*1)
        Assume s belongs to L(0(0+1)*0) then by definition of the language denoted by R, s is in the form
        tuv where t belongs to L(0), u belongs to L((0+1)*), and v belongs to L(0).
        Same for the case that s belongs to L(1(0+1)*1).
        Thus s begins and end with the same bit.

    In all 4 cases, s begins and ends with the same bit, so s belongs to L
    As s is chosen randomly in L(R), we get the conclusion that every element of L(R) is also in L; that is, L(R) is subset of L.

Suppose s' is an arbitrary element of L, then we consider 2 cases: | s' | = 1 and | s' | > 1.

    case1: | s' | <= 1 =>  | s' | = 1
      The lone binary string of length 0 has neither a starting nor an ending bit to be the same as anything.
      A binary string of length is either 1 or 0 so it belongs to either L(0) or L(1). Since both L(0) and L(1) are subset of L(R), by inspection s' belongs to L(R).

    case 2: | s' | > 1
      In this case, the starting and ending bit of s' are the same but internal elements are different in s'. So s' is the form tut, where t belongs to L(0+1), and u is an arbitrary binary string over
     {0,1} , that is u belongs to L((1+0)*).

     We may ssume t belongs to L(0) as the same arguments follows if we interchange 0's for 1's.
     In this case, s' belongs to L(0)L((0+1)*)L(0) which belongs to L(R), so s' belongs to L(R)

   In both possible cases s' belongs to L(R). Since s' was choosen randomly, then every string of L is also a
   string of L(R). Hence, L is subset of L(R).

Since L(R) is subset of L and L is subset of L(R), we get the conclusion that L = L(R).

DFSA

This week, we introduced 2 new topics - formal language and FSAs. Basically, a formal language is a set of strings of symbols. FSAs, which stands for finite-state automaton, is a mathematical model of computation used to design a sequtial logic event.

Here is a easy and interesting example that is useful for understanding the topic.

Question: Devise a DFSA that accepts the language of a finite binary string whose length is a multiple of 3.

Solution:
My answer is as following:

where q0 is both the inital state and the end state because 0 is a multiple of 3 as well.
Every time after 3 numbers added (a multiple of 3), we reach the accepting state q0. 

bad term test

It was really bad unlike the first one because we have not much time to do it. Only fifty minutes for an unwinding, and 2 long proofs. Most of my friends had the same feeling, so I hope we would receive bell-curve.

An interesting question on the term test was to prove that 

c0 lg n <= T(n) <= c1 lg n which implies T belongs to big-theta (lg n).

To prove this question, I used the following structure

case1: c0 lg n <= T(n) 

           ...

           Then case 1 holds

case2: T(n)  < = c1 lg n
           ...

          Then case 2 holds

Then since both cases hold, we conclude that c0 log n <= T(n) <= c1 log n.
Then T belongs to big-theta (lg n)

Master Theorem

Today I learned Master Theorem. However, there are not many explanations on the course slides. I was still confused after I read the course notes because it doesn't mention what "d" is in the definition. So I found the clearer (for me, and hope helpful for others too ) version of Master Theorem here:

For the definition of T we have, we can easily use Master Theorem to find the bounds of T without unwinding.

In summary, when we have a definition of T and want to use Master Theorem, we do the following steps:

1. calculate n^log_ba

2. compare if f(n) either greater, less than or equal to n^log_ba
        if f(n) = n^log_ba , then T(n) = θ ( n^log_ba lg n)
        if f(n) < n^log_ba , then T(n) = θ ( n^log_ba)
        if f(n) > n^log_ba , then T(n) = θ ( f(n) )

The summary above just for general case, and understanding. For preciseness, please refer to the Theorem 4.1. =]

term test1 result and Predicate of Induction

I got my term test1 result today. I felt not bad when I just finished the test because I knew how to do every question. However the grade was not good for me. I made a mistake that shouldn't have happened.

As we made a predicate in such form "P(n): For every n belongs to N,13^n-1 = 12y where y is also a natural number. We prove that for all n belongs to N, P(n) by Mathematical Induction". We define what P(n) exactly is in this question, then we indicate that for all n belongs to N,P(n) and what type of Induction would we use. However, I wrote "P(n): For all n belongs to N,  and all y belongs to N,13^n-1 = 12y." which is completely wrong because we should use INDUCTION to do it . Then we can't say all n belongs to N inside the definition of P(n).

It seems like a stupid mistake. The test consists of 3 question and 5 marks each. It cost me 1 mark for every question. So due to this little problem, I lost 20%! I am so depressed about it. =[. That is my fault. I will do better next time and I won't make such a low level mistake any more! I will do better next time.