Overall thoughts on csc236

We just had our final lecture in csc236 and have finished wrapping up the loose ends of the course material. With only one test left and then the exam, it's safe to say were basically finished the course. In many ways I greatly enjoyed csc236 more than most of the courses i've taken so far. The course material was interesting and I thought that the lectures were properly allocated to effectively cover the required material. I found the lectures to be extremely informative, especially because of how we went through examples together, and an effective way to learn the material. I surprisingly liked the weekly problem sets and thought they were a good way to keep ontop of the material. I also started using the help center and went to office hours more often (Heap center?), both of which I found to be of great help when I got stuck on certain points of the assignment. If there were areas to improve the course I'd suggest for next year, I'd like to see more of how some of the concepts are applied to computing, i.e how are DFSA's used in programming, though I don't believe it should be too indepth. I'd also like to have a bit more of the class time afforded to converting NFSA's to DFSA's and on context-free Grammar, but I understand that the lack of class time dedicated towards these topics was more likely a result of us just being introduced to them for next year and then expanding on them then.

Context free grammar

Context-free grammar (CFG) describes how sentances in a language are built recursively using a set of rules, the operations given as variables on the left hand side of the equation and the nouns, verbs, etc given as terminals on the right. After doing the exercises in class, I found I had little trouble with the concept. I think I found the concept to be very natural and intuitive after doing DFSA, as the motivations behind the rules seem similar. I decided to look up more about the limitations and extensions around CFGs. An interesting example of an undecidable language, one for which a CFG does not exist, I stumped onto was the case of language that accepts every string. Extending this, it seems that it is in many ways undecidable if two CFGs, that are not precisely equal, describe the same language. I also found it interesting how people had extended the power of CFGs by allowing the nonterminal elements to have arguements, which allows for natural language features such as references and agreement. I'm interested also in seeing how context sensitive grammar works as well as how CFGs are used in computers.

Pumping lemma

The pumping lemma is a tool that we use to determine if a language is regular. In laymen's terms, the idea of the pumping lemma is that an accepted string past a certain length can be broken into parts and that no matter how many times these parts are repeated, the string will still be accepted by the language. More formally, If L is a regular language. Then there is some p that depends on L such that if x is an element of L and |x|>= p, then there exists substrings u,v,w such that x = uvw, where |uv| <= p, v is not empty , and for all k in the Natural numbers, w(uv^k) is an element of L. However, I am unclear on certain aspects of using the pushing theorem. The most trouble I seem to have is with how to break up the string x into uvw and whether we must consider all possible strings u,v,w that could collectively form x. Additionally I can see that a language that does not have the pumping lemma property is not regular, but I am unsure if a language that has the pumping language property is necessarily regular. After searching the internet a bit, it seems that the property apparently holds for some irregular languages, for example, (taken from the wikipedia page on pumping lemma for regular expressions): the language {u(u^R)v : u,v {0,1}+} (strings over the alphabet {0,1} consisting of a nonempty even palindrome followed by another nonempty string) is not regular but can still be "pumped" with p = 4. Suppose w=u(u^R)v has length at least 4. If u has length 1, then |v| ≥ 2 and we can take y to be the first character in v, thus not affecting the palindromic requirement. Otherwise, take y to be the first character of u and note that yk for k ≥ 2 starts with the nonempty palindrome yy, so it's still in the language. I would like to see a bit of attention paid to this example in class, because it seems to be an interesting example of where the pumping theorem may fail.

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.