DFSA? NFSA? Regular Expression!

I've found the question on DFSA and NFSA quite interesting. It seems straightforward to me yet when it comes doing the drawing it becomes a different story. I managed to find the question about DFSA and NFSA from the old 236 course so we'll go over them today.

I realized it'll be nice to have some basics explained here. First there's a more introductory question that I found in the past tutorial paper in the CSC236 course website.

List the elements of {a,ab}*.  Find a way to describe strings in this language, i.e., find a predicate P(s) such that P(s) is true iff s in {a,ab}*, for all strings s over alphabet {a,b,c}.

    Q:  What's {a,ab}*?
    A:  {a,ab}* = {e} U {a,ab} U {aa,aab,aba,abab} U {aaa,...} U ...
                = {e,a,ab,aa,aab,aba,abab,aaa,aaab,aaba,aabab,...}

    Q:  How can we describe strings in {a,ab}*?
    A:  This is almost like {a,b}* (all strings of a's and b's), except
        each 'b' comes with an 'a' in front, i.e., P(s) = s is a string
        of a's and b's where each b is immediately preceded by an a.

    Q:  We're done, right?
    A:  Almost: we should check that s (- {a,ab}* iff P(s), by arguing
        each direction:
        =>  It is obvious that each string in {a,ab}* has property P()
            (every b immediately preceded by an a).
        <=  Moreover, each string where each b is immediately preceded
            by an a belongs to {a,ab}*: the string can be broken up
            into pieces 'ab' (one for each b in the string) with every
            other symbol being 'a'.

Time complexity & Master Theorem & Repeated substitution

Time complexity and repeated substitution are the materials I found challenging in this course. It was first introduced to me last year in CSC165 as big O and big Omega. At below are some example questions I found that were quite challenging to me. I'll hence go over them in a detailed way.

Consider the following recurrence relation.  

        T(n) =   { 2                                     if n = 0, 1
                     { T(floor(2n/3)) + lg(n)     if n > 1

    Find upper and lower bounds on the value of T(n), using the Master
    Theorem.  Then try to find a tight bound.

 * This is a trick question, because the Master Theorem only applies to
    recurrences where the extra work performed outside the recursive calls
    takes time \Theta(n^d) for some constant d.  

    Nevertheless, we can use the Master Theorem to obtain separate upper
    and lower bounds on the value of T(n).  Consider the following
    recurrence relations.

               
        L(n) =        { 2                     if n = 0, 1
                          { L(floor(2n/3)) + 1    if n > 1

                             
        U(n) =      { 2                               if n = 0, 1  

                         { U(floor(2n/3)) + n    if n > 1

    Since 1 <= lg(n) <= n for all n > 1, it is easy to see that for all n,
    L(n) <= T(n) <= U(n).

    Applying the Master Theorem to L(n), we get a = 1, b = 3/2 and d = 0 so
    a = b^d and L(n) (- \Theta(n^d log n) = \Theta(log n).
    Hence, T(n) (- \Omega(log n).
    In this case, it would be trivial to prove T(n) >= lg(n) by induction on
    n >= 1-- it may seem that the inductive hypothesis is not necessary, but
    it is to ensure that T(floor(2n/3)) is not negative.
    { Go over this proof at the end of you have time left-- but don't worry
      about it if you don't. }

    Applying the Master Theorem to U(n), we get a = 1, b = 3/2 and d = 1 so
    a < b^d and U(n) (- \Theta(n^d) = \Theta(n).
    Hence, T(n) (- O(n).
    Again, it is trivial to prove T(n) <= 2 n by induction on n >= 1--
    making use of the fact that lg(n) <= n for all n >= 1.
    { Go over this proof at the end of you have time left -- but don't worry
      about it if you don't. }

    Unfortunately, we have reached the limit of what can be learned by
    applying the Master Theorem-- there is no way to make the bounds any
    tighter.
    { Well, that's not quite true: if we remember that lg(n) is o(n^c) for
      any realy number c > 0 (from calculus), then we can prove that T(n) is
      O(n^c) for any real number c > 0.  But that still leaves a gap between
      the upper and lower bounds. }

    In order to get a tight bound, we need to use something like the
    repeated substitution method.  We will need to use the following facts
    about logarithms-- it is assumed that you are aware of these properties,
    and you are allowed to make use of them in your own work.  For all real
    numbers x, y > 0, and all bases b > 1:
      - log_b(x/y) = log_b(x) - log_b(y)
      - log_b(xy) = log_b(x) + log_b(y)
      - log_b(x^y) = y log_b(x)

    Repeated substitution for T(n):

        T(n)     =     T(2n/3) + lg(n)
                    =     T(2(2n/3)/3) + lg(2n/3) + lg(n)
                    =     T((2/3)^2 n) + 2 lg(n) + lg(2/3)
                    =     T((2/3)^3 n) + lg((2/3)^2 n) + 2 lg(n) + lg(2/3)
                    =     T((2/3)^3 n) + 3 lg(n) + 3 lg(2/3)
                    =     T((2/3)^4 n) + lg((2/3)^3 n) + 3 lg(n) + 3 lg(2/3)
                    =     T((2/3)^4 n) + 4 lg(n) + 6 lg(2/3)

        after i substitutions,

                   =     T((2/3)^i n) + i lg(n) + (i (i-1) / 2) lg(2/3)

        T( ) "disappears" from the right-hand side when (2/3)^i n = 1, i.e.,
        i = log_{2/3}(1/n) = log_{3/2} n.  For this value of i,

        T(n) = T(1) + log_{3/2} n lg(n)
                 + (log_{3/2}(n) (log_{3/2}(n) - 1) / 2) lg(2/3)

    Based on this, we expect that T(n) (- \Theta(log^2 n)