Revision of regular expressions

Regular expressions are a precise and succinct notation for describing languages.
For regular expressions, there are few symbal that can be eazily defined.
"+" means "or"
if two letters are together then they are listed in order
"*" means can be none or repeat any times.
"()"means the formula inside should be consider first.

Examples:
1* will be a binary string with only 1s or empty string
1+0 will be 1 or 0
(10)+(1+0) will be 10 or 1 or 0

There are Precedence rules for reducing the number of parentheses used.

A regular question will be devise a regular expressions R for a set L and prove it.

Questino:Let L be a set of binary string start with 0 and end with 0.Devise a regular expression, R that denotes L, and prove that your regular expression is correct.
For doing this kind of question, we need to find several elements in the set first.
we know that empty string is not in the set cause it doesnt has a number 0.
so the first cases will be 0 and others can be 00 010 000 0110.
So we know that expect for the first cases others will be 0+any binary string(include empty string)+0 (+ means plus here)
So the first part of the R will be 0+.
The another part will be 0(0+1)*0 as (0+1)* represents any binary string.
So R=0+0(0+1)*0

Then we have to prove that for any x ∈L, if and only if x∈L(R)
which means L=L(R)
we need to prove that in two ways that
L belongs to L(R) and L(R) belongs to L.

Well, I still dont know it clearly how to do it in correct way for this step. May have to learn it in next lecture.

How to draw a diagram of DFSA

A deterministic finite state automaton (DFSA) is a mathematical model of a machine which, given any input string x, accepts or rejects x.
In other word,if u give an input string x ,following this model will tell u if the string x works or not.
Example:Devise a DFSA that accepts the language of fi nite binary strings with odd numbers of 1's.
What we do in the normal life is just counting how many 1's are there in the binary string. But for a function or a program, the machine will have to go through all the number from the first till the end.
We have to count how many states are there for this model first.
As for this example, they are only 2 states:
a)odd number of 1's (accepting state)
b)even number of 1's
Think as a machine,we may start from the first number in the string.
But, we have to consider the starting state that even the first number has not been considered.
Appearently ,an empty binary string has even number of 1's (0 1's).
Then we know that if the next number is 1 the total number of 1's will change to another state. However 0 doesnt change the state.
The diagram will be :

And q1 the accepting state.
From the graph we know that a number 0 doesnt change the situation of whether the string has even or odd number of 1's.
So we can simplify it to

 

Now we are done!

Term test and T(n)

Hope that I will get a good mark.
_(:з」∠)_

The term test2 is pretty much similar to the old term test but withonly 2 questions. I arrived late but got the exampaper at the right time.
After glancing the exam paper. Question may not be as difficult as I had thought before.Now I totally forgot what I wrote but I remember it was all about T(n).
However the first question asked us about proving correctness and termination.
I was trying to prove termination first but then I realized I can put them together. But from the lecture, they should be proved individually. I wish I didnt lose too many marks cause of that.
In my opinion, precondition is like the input of a function and postcondition is the output in other words.
Precondtion=>function terminate=>Postcondtion. It just like domain and range in mathematics.

Master Theorem (for divide-and-conquer recurrences)will determine T(n).
When T(n)=aT(n/b)+f(n) where
n:the size of the problem.
a:the number of subproblems in the recursion
n/b: the size of each subproblem ,d: the cost of the work done outside the recursive calls
f(n):the cost of the work done outside the recursive calls.
and T(n) will be different when a,b,f(n) changes.
It is not same as what we have learned but it is pretty similar.
I think I will keep working on this and fully understand it.

My way of finding closed form Fibonacci numbers

It seems impossible to use repeated subsitution.
Then do it mathematics way.

sqrt():square root of a number.

Assume  H(1)=a1=1 H(2)=a2=1

              H(n)=a_n=a_n-1+a_n-2

   Suppose a_n+αa_n-1=β(a_n-1+αa_n-2)

         When a_n=(β-α)a_n-1+αβa_n-2

         Compare two equation and get

        β-α=1

         αβ=1

 suppose α>0, β>0

      α=(sqrt(5)-1)/2

      β=(sqrt(5)+1)/2

since a_n+αa_n-1=β(a_n-1+αa_n-2) it is geometric progression.

So a_n+1+αa_n =( a₁+αa₂)β^n-1

                 =(1+α) β^n-1

                  =βⁿ

Suppose b_n=a_n/βⁿ

And suppose b_n+1+λ=-α/β* (b_n +λ)

λ=-1/(α+β)

since b_n+λ=(-α/β)^n-1(b₁+λ)

then b_n+λ=(-α/β)^n-1(1/β+λ)

then get a_n=sqrt(5)/5 *{[(sqrt(5)-1)/2]ⁿ+[(sqrt(5)+1)/2]ⁿ}

then H(n)= a_n=sqrt(5)/5 *{[(sqrt(5)-1)/2]ⁿ+[(sqrt(5)+1)/2]ⁿ}

It was so hard to calculate so I put it on blog in order to learn it by heart.

My way of doing recursion problems

Usually, you always need to think more about recursion problems than induction problems.
The reason is: for induction problems you always consider the nth case (or first to nth)to imply NO.(n+1) case.But for recursion, you have to think from nth case all the way down the first case and then prove it by induction.

Use repeated substitution (unwinding) to find a closed form for the recurrence S when n is a power of 3:
          1 if n < 3
S(n) = {
          a1*S(ceiling[n/3])+ a2*S(floor[n/3])+sqr(n) if n>2
... where integers a1,a2≥0 and a1 + a2 = 3.

The question gives the condition of n always related to other factors.
You can find n is a power of 3 and ceiling[n/3] floor[n/3]
Since n is a power of 3 which means n=3^^k.
Then try to substitute n=3^^k into S(n) when n>2.
Because n is a power of 3,ceiling[n/3]=floor[n/3]=3^^k-1
Then S(n)=3S(n/3)+n^^2 which is 3S(3^^k-1)+n^^2

substitute again then will be able to find S(n)=9S(n/9)+n^^2/3+n^^2

keep substituting until get S(n)=n+3/2n(n-1)

then prove it by induction.

The key point is to find the realtionship between S(n) S(n/k) S(n/k^^2)....and at the end S(1)

Questions about complete induction.

We all know that complete induction is (P(0),P(1),P(2)...P(n)=>P(n+1))=>P(n).
Is possible if i use (P(1),P(3),P(5),...P(n+1)=>P(n+3))=>P(n), but i said before the induction steps that n is a odd positive integer.

My way for doing induction problems.

 Proof questions are nightmares for most student.

There are two way--mathematical induction and complete induction for solving different problem.
However, I find using mathematical induction more often than using complete induction.
What 3 steps I used for proving statements:
First step: Define P(n).
  In order to do so, I will read question really carefully to get what kind of  P(n) I have to define and what n means in P(n).

Examples:
the square of b is greater than double of itself when b is a natural number greater than 2.
then P(n) would be: sqr(n)>2n.

Second step:Finding base cases for P(n).
  For this step, always find the eaziest case but the smallest case that P(n) is true. That u will be able to find the range of n.

Examples:

For sqr(n)>2n.
Find P(n) is true for n=3.

Third step:(most important steps)Induction steps
For mathematical induction using P(n)=>P(n+1) to prove all n is true for P(n)

Examples:
  if P(n) is true. then prove P(n+1)
       for the examples about just to find the different between sqr(n+1) and sqr(n) is greater than or equal to 2(n+1)-2(n).


Complete Induction has first two similar steps but the third steps will be (P(0),P(1),...P(n)=>P(n+1)) =>P(n).

That is how I did for proof questions using induction method.