where's my A+!?

For the last 2 to 3 months, i have constantly spent my time complaining about assignments and tests! a heavy load of works. However, at this point of facing close to the end of the term and courses, i wish i could have those time back and spend them wisely, try more questions and readings rather than just complaining and waiting something that i would never come into my head without any efforts 

i know everything is ending and our course as well, but!! NOT yet... i just started understanding the  course material, which i know, is way too late  ridiculous! but i've got the final exam left, i'm sure i can do well on it! 




                                  

  KEEP CALM AND SMILE BIG!!

thank you for reading my posts!

From FSA to regular expression

with given a FSA model, M, we can construct a regular expression that denotes precisely the language accepted by M.

Question.2 from tutorial exercise #8  

From the DFSA, shown in the previous post of "DFSA example";

devise the regular expression that denotes the same language.

the DFSA to start with:

- Remove every state except the accepting state and the initial state.

first, try to remove q3 state; x has an odd number of 0s and an odd number of 1s

then we get a DFSA

then, we remove q2 state; x has an even number of 0s and an odd number of 1s

then we get a DFSA

Devised the regular expression:  

                                          

This particular tutorial exercise question really got me to understand, how devising a regular expression from FSA, works! thanksful ^^; 

DFSA example

:Devise a DFSA that accepts the language of strings over {0,1} with an odd number of 1s and even number of 0s.

              

              

DFSA

DFSA stands for deterministic finite state automaton and is a mathematical model of computation used to design sequential of states logic circuits, which given any input string, x, accepts or rejects x. 

- a machine has a finite set of states, including a designated initial or start state and a designated set of accepting states.

- the machine is in only one state at a time; the state at any given time is called the current state. changing states from one state to another is called a transition.

- the machine stops when it has processed the entire input string in a manner of one symbol at a time.

- when it stops, if the current state is in an accepting state, it accepts the input of a string; otherwise, it rejects the input.

Correctness

Correctness of Iterative and Recursive functions

A program is said to be correct, if it produces a correct output on every acceptable input, which, in terms of the proof terminology, means that for all possible inputs that satisfy the precondition, the program produces an output that satisfies the postcondition.

Precondition: an assertion that states what must be true before the program starts execution
Postcondition: an assertion that states what must be true when the program ends
                       - in particular, it can describe what is a correct output for the given input.

if a program meets both precondition and postcondition, then we say the program is correct.

Partial Correctness
- prove that if the precondition holds before the program starts then the following is true at the end of each iteration of the loop.





Loop Invariant 
- a statement that is true on entry into a loop and that is guaranteed to remain true at the end of every iteration of a loop.

Divide and Conquer

Divide and Conquer recurrences

Definition from the lecture week#7:
The very general idea of divide and conquer proof is to partition a problem into b roughly equal subproblems and solve them and then recombine to prove the desired bound on the function based on the already defined subproblems.

- General template for a divide-and-conquer proof

A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the related type until these become simple enough to be solved directly. The solution to the sub-problem are then extended and combined to derive a full solution to the original problem. 

Probably this would be the most difficult material of the course i have ever faced with by so far. To prove one recursively defined function with a technique of a divide-and-conquer requires not just one but two or more broken down steps to come up with a solution to the original problem.

Unwinding; Week#6

Example of recursively defined function:

defines the value of the function at some natural number n in terms of the function's value at the previous number, n-1, whereas the function at 0 is explicitly given. 

- we would refer to the first part of the definition as the base-case and to the second part as the inductive step of the recursion. 

when proving a recursively define function, first thing we would have to do is the step called "unwinding", which derives to find a closed-form formula for a function, f(n).

How-To-Do: we unwind(a technique called repeated substitution) the recursive definition of f(n) by simply repeatedly applying the induction step of the definition to smaller and smaller arguments of function(recursive steps), f. we keep this step until we discover a pattern that will convey us a closed-form formula. 

1.  find closed-form formula for the function by using unwinding technique

2. prove that the closed-form formula is equal to the recursive definition of the given function by using an appropriate induction.

CompleteInduction-Example

Proof. We prove by complete induction that any amount of at least 8 cents can be made by using 3 cents and 5 cents. The induction hypothesis, P(n) will be:

 there is a collection of coins whose value is n + 8 cents.

"simply follow the template given in the previous post about complete induction."
"very similar to the Postage question we did during the lecture"

BaseCase: P(0) is true because a 3 cent coin together with a 5 cents coin makes 8 cents

Inductive Step: We assume P(m) holds for all m <= n, and prove that P(n+1) holds. There are two different cases; we prove by cases

Case 1. (n+1=1), then (n+1)+8 = 9 cents, we can make 9 cents by using 3 x 3 cents = 9 cents
Case 2. (n+1=2), then (n+1)+8 = 10 cents, we can make 9 cents by using 2 x 5 cents = 10 cents

Case 3. (n+1 >= 3), then 0 <= n - 2 <= n, so by the complete induction hypothesis, for n-2 cents amount can be made. Now by adding a 3 cents coin; n-2 + 3 = n+1 can be made

Conclude that P(n), any amount of 8 cents or more can be made out of 3 cents and 5 cents coins, holds for every positive natural integers, n.

Well-Ordering Induction

Template: Well-Ordering Proofs

Stating the template for a well-ordering proof steps would be adequate to give general explanation of its definition;

- Define the set, C, of counterexamples to P being true

- Use a proof by contradiction and assume that C is non-empty

       contradiction definition: 

       a form of proof that establishes the truth or validity of a proposition by showing that the         proposition's being false would imply a contradiction

- By the well ordering Principle, there will be a smallest element(introduced a new variable), n in C.

- Reach a contradiction (somehow) - often by showing how to use n to find another member of C that is smaller than n.

- Conclude that C must be empty, that is, no counterexamples exist.

Complete Induction

Complete Induction

only minor difference from a mathematical Induction is that it allows us to assume more than just P(n), whereas, in a mathematical induction, we only assume that P(n) is true and try to prove that P(n+1) is also true.  In the inductive step of our complete induction proof, we may assume P(0),P(1),....,P(n) are all true and based on our assumption, we prove that P(n+1) is also true. 

A Template for Induction Proofs:

1. State that our proof is by complete induction to convey the overall structure of the proof of our upcoming arguments and statements.

2. Define an appropriate predicate P(n)

assume that P(0),P(1),...P(n) is all true. The eventual conclusion of the induction proof will be that P(n) is true for all positive n. Thus, we should produce the predicate P(n) so that follows from the conclusion. Often, it can be derived from the proposition that we are trying to prove. 

The predicate P(n) is called the Induction Hypothesis.

3. Prove that P(n) is true. This step of the proof is called the Base-Case(or Basis); showing that the statement holds when n is equal to the lowest value that n is given in the question.

4. Prove that P(n) implies P(n+1) for every positive natural integers, n. This step of the proof is called the Inductive Step.

by assuming the induction hypothesis, then use this assumption to prove the statement for n + 1; this step requires some ingenuity and appropriate mathematical approach.

5. Based on the facts that have been made in the previous steps, we may conclude that P(n) is true for all non-negative integers, n. 

think the induction as the domino effect:
1. the first domino will fall
2. whenever a domino falls, its next neighbor will also fall 
- P(0) -> P(1) -> P(2) -> P(3) -> ... -> P(n)
then conclude that all of the dominoes will fall; P(n) is true for all positive natural integers, n

TheFirstAssignment! Due

The first assignment from CSC236 was not as difficult as i thought it would be, but definitely required hours and hours of time-efforts. 

The main obstacle that i have encountered with the course at this point is that even thought i have clear understanding of concepts of course material such as the Induction and every steps make sense and i can sort of grasp the whole idea and follow along. However!! with a given example or a problem, i found very hard to figure out the inductive step of where by using induction hypothesis, i am supposed to make a appropriate approach to show connection between the gap of implication of P(n) to P(n+1) with ingenuity and suitable mathematical approaches.

the most parts of the assignment was done by Danny during the lecture, i just had to follow what he had done but needed to make modifications to them but not too hard since i was given with basic frame of the proofs.ThankYou!

i really hope to get a good grade on this, which would indicate well-to-do within the course later . 

Mathematical Induction

Mathematical induction, also called simple induction, is a method of mathematical proof usually used to prove that a given statement is true for all nutural positive numbers. This induction seems to me as one that is, by far the most powerful and commonly-used proof technique in computer science and mathematics, and SIMPLE!! as the name tells.

the Principle of Simple Induction

- Establish that the property is true at the starting point(Predicate), simply prove that P(n) is true
- Establish that the property spreads from each natural number to its successor:

explanation:
Let P(n) be a predicate. If:
- P(0) is true, and <- BaseCase
- P(n) implies P(n+1) for all non-negative integers, n. <- Induction Step.

Nothing too complicated about this induction. We've already covered this in the previous course of CSC165. But sure it is definitely important to have a clear understanding of this fundamental and essential one-of-kind induction. 

Back To School Back To SLOG

This is my whole new beginning of a journey to be success in the course,
                                             
"Introduction to the theory of Computation"

I thought of this idea of making ourselves a Blog"SLOG" is great in terms of that, this can actually give us an opportunity to keep track of our improvements and developments within this course, when looking back the posts that we have made after a certain time passed.

while writing posts, these are the things i would look forward

1st. i hope while writing posts on the course material, i would gain more clear understanding and insight of the concept. Probably this would be a good opportunity for me to review what i have studied and check whether there is any misunderstandings or things that i have missed while studying specific topic.

2nd. by posting my experience and my thoughts on the course, i would share mine with other classmates, such that i can actually be part of this course's community and feel like we're actually moving forwards to where we say "success" together with everyone in this course.

3rd. to keep up with posts, i would have to do certain amount of research and study in order to write posts, which prevents me from being behind from course materials and lectures. ThankYou!

I guess everyone in this course who are working their best to do their best has one thing in common!!!
becoming fulfilled in this course with a decent grade, which requires time and efforts.

i would expect nothing from this course if i don't deserve to have them!! No Give-Up No Lazy

i will try my best and the best for the rest of the term.