Converting FSA's to RE

We just finished looking at the mechanism for converting a DFSA to a RE in class. The general idea is to observe the pathways of which each state reaches and exits a particular state and formalize a statement that describes those movements. In doing this we are able to eliminate that particular state and as we repeat the process we eventually remove all the states and are left with a single expression. However, this expression tends to be incredibly complex. Although the expression works and the process is intuitive enough, i'd like to see more examples of simplifying the regular expression that emerges form the process.

DFSA

As we begin to move towards the end of the course, we've largely just finished wrapping up the lectures on deterministic finite state automaton. With the last question one the assignment having us make use of the Cartesian product, some of the important advantage and disadvantage of using DFSA to recognize strings as part of a valid set of languages have become clearer. Particularly, the process is extremely, and quite possibly only, effective when the DFSA is dealing with simple languages. The disadvantage becomes clear when we consider the number of transitions states required as the alphabet increases in size and how the problem space of the method falls prey to combinatorial explosion with small increases in the alphabet size. Infact, it seems as though the complexity of the set of strings accepted languages, perhaps measured by the number of operations involved in the equivalent regular expression, causes the problem space of the DFSA to approach combinatorial explosion as well. Thus, I suspect that the limitation on the complexity of both the language and the alphabet that a DFSA can represent is severely limited or else it requires that the statement be broken up into many smaller machines, the intersection of which is the original regular expression, a process that seems infinitely more tedious then should be necessary. Ultimately I'm curious how DFSA are used in modern computing and how we ensure the stability of their use.

Regular expression

It's extremely fascinating to see the differences between artificial and natural languages. Given the often times unnecessarily cumbersome and ostentatious feel of the rules English, I often find myself appreciating the sublime beauty found in the simplicity of artificial languages. As I begin work on assignment 3, I find it striking how powerful a tool regular expressions can be. I found the concept a bit confusing in lecture, specifically when proving facts about languages, but having worked through a few examples from class i'm beginning to become more confident about the, Having experimented with Regular expressions for searching through text files for the upcoming 207 exercise, i'm beginning to wonder how I ever lived with the incredibly bare bones default find function. If artificial intelligence ever becomes truly self aware, it's comforting to know that their superior powers of communication will help them subjugate our race.

Loop invariants

Since an invariant is An assertion that some property must always hold, one easily comes to the conclusion that a loop invariant is a property that is always true for the duration of the loop. Having just finished covering loop invariants in this weeks lectures, I began to try and apply the concepts we had learned about program correctness to the next assignment I had gotten from csc207. By and large I found it to be an incredibly helpful, albeit time consuming, way to ensure that my functions were closer to success on the first draft of code and that they were overall more successful and stable in the final draft of coding. I'm also hopeful that, since I took a much more rigorous approach to convincing myself my code would work, I should be able to provide much more useful and insightful documentation for my code.

We also had the second midterm, I find that i'm studying far less for csc236 then I had for csc165, but am understanding the material much better and thoroughly. Last year I found myself devoting more time to attempting past tests to understand the material, rather then reading over the course notes I had made, and ultimately I feel it was a far less effective study method. As I continue to refine my study techniques I find myself far less stressed out for midterms, to the point where I found myself appreciating the cleverness of the code in the question where the code checked the parity of vowels in strings.