Context free grammar

This morning was particularly refreshing. Maybe because I've slept earlier than usual. I was able to get a good grasp of Danny's lecture today.

Our topic today is "Context free grammar". I find this topic interesting in particular because we've been learning about symbols, strings and languages. The topic couldn't have been complete without being able to create proper sentences out of all the languages and symbols that we've defined.

The symbols V,\sigma, P,S all are part of G (grammar). The symbols are broken down as the following:

V - the set of variables
\sigma - the terminals
P - the set of production (rules on how a sentence can be constructed)
S - the starting points

Danny then gave us an example of

G1 : S -> 0S1
S -> \epsilon (empty string)

When I saw this expression, I jumped to the conclusion that the only possible answer was 01. However, analyzing closer at this expression tells us this is not true because S can also be 0S1. Thus, it could mean (0*1*). I feel that though this lesson I have more insight to regular expressions but the way the language of the grammar is still unclear to me.

For example:

L (g) = {alpha | S=>*g x} (Note: * is super script and g is subscript of the implication arrow)

My understanding is that S follows the grammar "g" and can be concatenated * times. Is this what it actually means?

Assignment 3

So in assignment 3, my most memoriable quesiton is #4 the DFSA question. I really enjoyed it because it seemed confusing to me at first but once I've got some of the confusion cleared up, it's actually a very trivial graph.

At first, I didn't know how to approach this problem because it contained 2 types of conditions that the string must abide by in order for it to be accepted. A TA pointed out to me that it would be wise to create 2 seperate machines which each will take care of one of the cases. So the first machine would take into the case of even or odd length while the second machine will process the multiples of 5. Then problem from then on was that this is a DFSA so how can 2 machines exist at the same time?

Danny did a real quick follow up on this part. In fact, the day after I've spoken to a TA regarding this question, Danny's lecture was about NFSA which is a FSA with no limit on the number of starting points. He then connected how NFSA can be translated into a DFSA and things were smooth from then on.

One major problem I've had as I was working on the multiples of 5 machine was that I didn't know what it means for a the transition of 0 or 1 given a string. I was able to get help from danny who explained to me regarding observations of what happens to the value of a binary number if a 0 is appended to it or a 1 is appened to it.

Overall, I feel a lot more confident that I've learned a lot from this assignment and all my trips to TAs and Office hours really paid off.

Problem Set 5

Yesterday I was working on problem set 5. Although what I had to proof was trivial but i didn't know where to start. Then my friend came in and we discussed on this topic together. In my mind I know that I can take the base case of P(0) where the string is empty since it is present in the alphabet this would make it true. However, I wasn't able to think of how I can prove for every string in the naturals after the base case. My friend Cy then gave me a hint that we can use the length to prove the rest. I then came to the conclusion using complete induction, we can prove for string with length k >=0, P(k) holds given the base case p(0). Thanks to him I was able to complete my problem set.

Regular Expression

I'm glad before entering university I've had the chance to play around with programming. I experimented with web based programming (php) and from peers online, I bumped into the topic of "regexp". I found it rather difficult at first because there were all sorts of symbols that I have to construct and understand in order to restrict a string to a desired format. I remember I was trying to create a form check for a valid email address and this appeared in many online tutorials. Although I don't have all the symbols memorized in my head I do have an idea of the more common symbols used (eg: * = zero or more occurance, + = one or more occurnace, \ = escape character, \w = [a-zA-Z0-9] characters and so on). Here I am right now studying regular expression which I think is a complement to what I've already known about regexp.

Danny gave an example of the alphabet of L = {0,1}. Our exercise in class was to prove L1 = L(1*(01*01*)*). Our approach to this type of problem is to prove that L1 is in the set of L.
To do this, we can join the two strings, one of which is the zero free prefix and the other is from zero to the end of the string. We then have one large string which then can be elaborated to be L(1*). Once that is expanded, we can then show that L1 is in the set of L and thus the prove is true.

Nested Loops: the final lesson

So friday was the day where we were taught the last of chapter 2 (recurrences and correctness).  The topic was nested loops.  The idea of this proof is very similar to proofing a regular loop except we have to start from the inner loop first as that will determine if the outside loop can run its next execution in the loop.

Looking at the code that was provided on the overhead by Danny, the class assumed that the precondition will hold and that the code will terminate properly.  The for this assumption is the loops within the selection sort have the condition to terminate once the interger variable reaches the length of the array. This happens for both the inner loop and the outer loop.  But to convince a skeptic that this actually works we can prove that the length of the outer loop is transitively the upper bound of the length of the inner loop.

The method that selection sort works is it takes a look at each element (we call i) and compare each element starting from the (i + 1)th element all the way until the end of the array to see if there is an element with a value less than the i-th element and perform a swap.  This means that the distance between the (i+1)th element is always decreasing.  The Distance between i and the length of the array is also always decreasing.  This proves that both loops will terminate when i or i+1 is equal to the length of the array.  The code then returns the sorted array.

Thus the code is proven to meet its precondition which is to loop through the array and perform a selection sort and that it will terminate implying that the code is correct.