My Last Blog

     

     The last week of classes was very helpful for me. It made me grasp the whole idea of the finite state automata and the regular expressions.

     Last week focused on connecting both the DFSA and regular expressions together. In class the Prof showed us some examples of how to draw the finite state automata, which we already learned, but then showed us how to get the regular expression from it. To get the regular expression we basically need to eliminate all states in FSA diagram one by one, except for the starting and accepting states. And finally we produce the regular expressions from the simplified version of the finite state machine.

     Over all I find CSC236 a very helpful productive course that will stay with us for the rest of the years to come.

     

     The exam is held next week. Planning to have excellent results in the finals; thus, I will go over my lecture notes, the course notes, and tutorial exercises. If I have extra time left, I will also go over the last midterm, tests, and assignments. 

Regular Expressions

A regular expression is a powerful search pattern that is used in programming. It helps identifying sequence of words, characters, or patterns of characters. Regular expression is used in many computer languages like python, java , c, c++.

CSC236 is focusing more on binary digits, strings of 0s and 1s and the different ways to express them by using different regular expressions.

Some of the important characters that are highly used in our course are:

*(star) : Repeats the previous item zero or more times.

+         : Repeats the previous item one or more times.

Here is an example:

Lets say we want to write a regular expression that accepts a string that contains multiple of 3  0s

To write the description of the language we can write:

L = s in {0,1}*| s contains multiple of 3 0s

It is easier for me to reach the regular expression wanted is to give myself examples of what should accept the description of the language and what shouldn’t

examples

empty string,  1, 11, 000, 0100, 101010, 0100000, 000100100010 accepts

0,00, 10, 1001, 10000, 0101010, 0000110 does not accept

So by looking at these examples I can say that all the 1s could be anywhere in the location and would not affect the final result of the language’s description

Only the 0s matter

Then      3 * 0 = 0

                3 * 1 = 3

                3 * 2 = 6

                3 * 3 = 9

                3 * 4 = 12

Thus we should have (0 or 3 or 6 or 9 or 12 or …. And so on) 0s. all are multiples of 3

If we have a string that contains only 0s then our regular expression should look like this:

(000)*  by following the definition of the *(star) from above

But it is not,  we need to include the 1s in which they should not affect the 0s

Then I believe our regular expression should look like this

(1*01*01*01*)*

        Since I already started learning regular expression in my other courses, I find that CSC236 helped me strengthening my understanding of the language, as well as it cleared many questions that were running in my head. 

Finite State Automata

We learned last week that we can draw/design/simulate computer programs and sequential logic circuits using FSM. The design is defined by a list of its states. We also learned that when you draw the FSM it starts at one point “current state” which can change to another state when initiated by a certain condition. Hence, Finite-State-Automata shows one state at a time.

In the example above, we can say if the starting state is q0 if we get z1 as input, then the state will change to q1. Or if the input is z0, then state will change to q3. If we’re on q1 and considered z1 as input then will keep the same state, or if input z0 then state will change to q2 and so on:

Current State                     Input                     Final State

q0                                           z1                            q1

q0                                           z0                            q3

q1                                           z1                            q1

q1                                           z0                            q2

q2                                           z1                            q3

q2                                           z0                            q0

q3                                           z1                            q0

q3                                           z0                            q3

                So far, I find the subject understandable and interesting  which will help me in my programming career. I still need to review the new definitions of "alphabet, string, and language" since they are new to me and would need to familiarize myself more with them.  

Pre and Post-Conditions

     Last week we have learned about program correctness and how to prove precondition and post-condition after each iteration.

     I find this very helpful and would benefit us in the future, especially for those who will be programming, not for only a specific program language but any (python, java, C+) it is a general knowledge to know if the code you wrote should run or stop somewhere in the middle. But with these proofs you should know for sure if the program will continue on running or stop.

     Here is an example from my last year’s lecture that made it easier for me to understand pre and post conditions and how to prove them:

Upper and Lower Bounds

I’ve learned last week about upper and lower bounds on functions and how to proved them I liked how the prof used big Θ in out assignment since it is a combination of both big O and Ω, in which we have learned in class.I like how we play with numbers to make our function greater than or smaller than the given timing depending on c or b in which is easy to find at the end of our proofs .

I believe as long as we know these rules we're good to go:

Also I’m getting more and more confident with complete and mathematical induction since everything in this course almost depends on them both

Still need to get familiar with upper and lower bound proofs

More on Recursive Functions:

     In this week we learned not only how to proof recursive functions but also how to define them. it is getting very complicated indeed, since it needs plenty of thinking it through and trying it out on many different values to make sure that you came up with the right formula for the recursive function. I find it a little easier to actually read the questions out loud and start drawing pictures or numbers on paper of the expected results. so if you have a better and easier way to do this, please let me know.

     After I do the above step and solve the problem I begin trying it with different type of values for (n) from smallest to some of the higher values. this was an example to help me under stand the whole divide and conquer recurrences from Introduction to the Theory of Computation book
the functions started looking like this:

   then it became in a closed form and looked like this:

then with mathematical substitutions we came out with the final T(n) that looks like this:

I hope for next week we won't take new topics and work more on these problems and on how to solve them.

Recursive Functions

The test for last week was OK, didn't get time to finish it though spent too much time one the previous questions. Therefore I learned that I should divide the time on all the questions accordingly

I read more about structural induction from the lecture notes and the 236 course notes, but still not sure if I understood the concept. Hopefully we’ll take more things on it in class

I find recursive functions very interesting, since you don’t get an answer right away you eventually need to break it down, then look and understand the relations between the changes then come up with the formula for how many times the function will run. For an example

Where n is greater than zero then we would break it up more

Let us use k = n

F(k) = f(k-1) +2k-1

 = (f(k-2)+2k-1-1) +2n-1= f(k-2)+2*2k-3

= (f(k-3)+2k-2-1)+4k-3= f(k-3)+2*3k-6

= (f(k-4)+2k-3-1)+6k-6 =f(k-4)+2*4k-10

.

.

.

= f(k-i)+2*ik-i^2-i

.

.

.

I like how we are still using complete induction and mathematical inductions to prove the recursive functions. Made my life a little bit easier. But I definitely will have to review theta and big O from last year.