Test3 and Final Words on CSC236

Test3 was a fair assessment of our knowledge of regular expressions and DFSAs,and I except a decent mark on it,although i feel i might have underwritten in terms of content for some of my proofs,but these mistakes will benefit me in the sense that i now know not to repeat them on the all important final exam.Finally,my last impressions of this course were that it was a very interesting,thoroughly enjoyable course,with an equally enthusiastic lecturer and some very unique and essential course content,which was all very surprising for me as i had heard really awful stories about other people's past experiences with CSC236,but am happy to admit,i found it be a very worthwhile and educational experience.I wish you all the best of luck on the final,and hoepfully will see you in CSC263 next semester.Take Care!!

My Polya Problem

For my problem solving session,i have decided to go back and answer Question 2(b)
of our 236 Assignment #3, using the Polya Problem Solving Techniques:

Step1:Understanding the Problem:

Firstly,i look at what the question has stated as given information,that the language L can be defined over a finite alphabet of {0,1},and any string that is represented in the language L has to have a even number of ones.Then,i examine the claim,which states that the Regular Expression R2 = (0 + (10*1))* can represent or denote the Language L.Now,my objective is to derive a proof that can substantiate this claim,or come up with a counter-example to disprove it.

Step2:Devising a Plan:

Once what has been given and what is to be proven is established,the first step I take would be to see if any counter-examples could be created,which would render the claim false.In this particular regular expressions case,there is no counter-example that would falsify the claim that R2 could represent L,since either 0 or 10*1,no matter how many Kleene-Star expansions are made(Kleene Star is a 0 or more repetitions of a character or string),both have an even number of ones,but that just means,the job is half done.Now,I have to examine a way in which to prove that this regular expression is capable of denoting L.One way to do this would be to show that if an arbitrary string is contained in R2,then it should be contained in L,and conversly,if it is contained in L,it should be contained in R2.This would show that R2 is capable of representing L.

Step3:Implementing the Plan:

Since I need to prove double implication,i.e x in R2=> x in L and x in L => x in R2,
a direction is needed to from which to begin the proof.For the sake of the problem,I chose to go in the forward implication direction first.
Forward:There,x is assumed to be aribitrary string derived from the regular expression R2=(0 + (10*1))*.Now,this string x can be broken up into 2 elements x[1]=0* and x[2]=(10*1)*.In each substrings case,they contain an even number of one characters,therefore when added back together,the sum of 2 even numbers get another even number,therefore the union of x[1] and x[2] would produce an even number of ones,which would allow x to be a member of the language L,Hence the Forward Implication is proven.

Backward:Here,x is assumed to be an aribtrary string in the language L,which means x must contain an even number of ones.Therefore,to form the x+1th string,the xth string can be concatenated with either the empty set,the set containing {0},the set containing {10*1}and the set containing {11} and the set containing {1},by the finite language over which L is defined.

Case1:If the xth string is concatenated with the empty string to form the x+1th string,then the x+1th substring would contain an even number of one characters,since the xth string is assumed to contain an even number of one characters,and the empty set contains no elements.

Case2:If the xth string is concatenated with the {0} string to form the x+th string,then the x+1th substring would contain an even number of one characters,since
the xth string is assumed to contain an even number of one characters,and the {0} string contains zero 1 characters.

Case3:If the xth string is concatenated with the {10*1} string to form the x+1th string,then the x+1th substring would contain an even number of one characters,since
the xth substring is assumed to contain an even number of one characters,and {10*1} contains 2 one characters,an even number of characters,which would hold true for any number of Kleene Star Expansions.

Case4:If the xth string is concatenated with the {11} string to form the x+1th string,then the x+1th substring would contain an even number of one characters,since
the xth substring is assumed to contain an even number of one characters,and {11} contains 2 one characters,an even number of characters,which would hold true for any number of Kleene Star Expansions.

Therefore,the x+1th string would always contain an even number of ones,and when any combinations of these Cases were made to form a new string,they would also contain an even number of ones since the sum of 2 evens is always even.Hence,The x+1th string can be represented in R2 since each one of these cases in representable by the definition of R2 itself.

Hence,since both the Forward and Backward Implications have been satisfied,R2 can represent the language L

Step4:Conclusion:

This thought-process represents structural induction,and the methidology behind which
most problems of this nature are solved.

Assignment #3,The last 2 problem sets and CFG(Context Free Grammars)

As we near the end of the semester,I have surprised myself to no end with my performance in this
course,which at the beginning of the semester was the one i was most reluctant to take,having heard nightmarish stories about its absurd difficulty,but through consistent work and with good instruction being provided by Danny,its proving to be my best course this semester in terms of grades and educational value.Hopefully,i will continue to ride this streak of good luck towards the end of the semester.Anyway,we completed assignment #3 this week,and while i was working without my regular partner on this one,I found the questions to be very gripping and a good test of essential concepts such as Program Correctness and Introduction to Regular Expressions.All in all, i expect a good grade on this one,and welcome any feedback.With regard to the last 2 problem sets,on which i scored 7/10 each,i felt i was less rigorous in my proofs then i have been in the past,and left a lot of small but essential arguments up to the marker to figure out,and that accounted for 3 very easily attainable marks.Oh well,you cant make an omelette without breaking some eggs!!:P.Both these problem sets dealt with manipulations of regular expressions,which have become my favorite part of this course,since they are very interesting when first glanced upon,and I'm sure that wherever they are applied,they must serve a greater purpose.Finally,this week we began CFG's(Context Free Grammars),which are an extension of Regular Expressions and formal Language,as in just as any language requires rules of syntax and grammar,formal languages and Finite State Automata require some sort of structure and regulation.Danny began his explanation with an example of a sandwich and how each element,when added in a certain order,makes a completely different meal every time,but still maintains the sense of being a sandwich.Looking forward to elaborate on this more as soon as i have caught up on lecture readings(since I've been coming habitually late to class this week!!).

Regular Expressions Continued(and Introduction to Finite State Automata)

This week,we began constructing Finite State machines,which are a very visual and extremely useful way of representing a Language.Firstly,we have the set of finite alphabet,normally denoted by sigma,and the transition function,which enables a Regular Expression or String to travel from one state to the next,denoted by delta,we have the starting state,where the machine itself gets inputted with the string,denoted by s,and a set F,which denotes the set of accepting states,which represent the output of the machine.Since we started with building a Deterministic Finite State Machine,there can only be a specific number of accepting states in F.Then,once all of this notation is established,we pass in strings that we think should be included in the language,and through tracing of the machines transition paths,we can determine whether the string belongs to an accepting state,and consequently the language.Also,the idea of efficiency was brought up,as there may be dead states,i.e non accepting states,or states that do not even lie on the path to accepting states,and these unnecessarily clutter and complicate the machine,so we get rid of them and the paths leading to them.We received our midterms back,and i was satisfied with my performance,but a note to myself for the future,i need to make my Precondition/Postcondition proofs a lot more formal.

Introduction to Regular Expressions and Midterm#2

This week,we had our 2nd midterm.I actually studied less for this midterm than the first one,and surprisingly,i feel i will fare much better on this one,Since the concepts covered in the midterm(closed form,precondition=>postcondition,loop invariant) have been ingrained into my head through countless iterations of the Assignment and problem sets.Also,in lecture this week,we began regular expressions,which entail creating a unique language consisting of certain characters(certain string,binary numbers etc),and using it in a program context to define certain algorithims.In my next post,i will go into more detail about this,as i am still no very clear on the subject yet.

Assignment #2 and beginning of Loop Invariant

Assignment 2 was due this Monday,and boy was it ever challenging.The question about the recursive formula for the number of ternary trees took me for ever to figure out,however by a combination of knowledge from STA247(at last some use from the course),and help from the T.A's at the aid center,We were able to finish it quite satisfactorily.Otherwise,in lecture this week,we began talking about loop-invariants,which are sort of relational tools in that they help you more fully understand the functioning of a particular loop.Personally,i am finding them a little bit strange to deal with right now,but i guess in due course,i will grow to understand them.

Midterm and introduction to correctness of a program

 The midterm was quite good,however i screwed up royally on one of the questions,while doing quite well on the remaining two.An overall estimation of my performance was that i knew what i was doing for the most part,i just did not follow through.hopefully,this will enable me to do better on the 2nd test.We began doing the correctness of a program this week,which was confined to two important properties,the precondtion which states what sort of input is needed for the program to be 'correct',and the postcondition,which states what sort of output stipulates a 'correct'program.Very interesting stuff.The other order of buisness is Assignment 2.Having done exceptionally well on A1, i now have to emulate the standard i have set myself on this assignment.