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)