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.