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.