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.