Polya Problem

Test 3, question 1.

The question described the machine that accepts odd length strings with a number of 1's that is 2 mod 3 (when divided by three has a remainder of 2). The first part of the question asked us to define, without proof, the state invariants and the second part asked us to give the state of the machine for a given extended transition function.

Step 1, understanding the problem:
The first part of the question asked us to define the states of the machine. For this part of the question I needed to understand the individual machines whose intersection formed the machine in the question. I then needed to find the Cartesian product of the two machines to get their intersection. Finally I needed to understand the transition functions of each machine, specifically which state they went to after seeing a certain input at a certain state. With these I thought I could describe the state transitions for the first part of the question and then use these to solve the second part of the question.

Step 2, devising a plan:
Since I had seen a similar problem on the third assignment, the machine that accepts odd length strings divisible by 5, I initially decided to approach the problem in a similar manner. Since the problem gave the transition of each state on a given input, I decided to use the one state invariant the question had given us to figure out the other 5. Once I had gotten the state invariants, I could use this information to determine the state of the machine for a given extended transition function for the second part of the question.

Step 3, implementing the plan:
I started by drawing out the individual machines. The machine for accepting odd length strings was simple enough, it had two states with a starting state for even length strings that transitioned on a 1 or a 0 to the accepting odd length string state and that transitioned back on a 1 or 0 to the even length state. The machine that accepts strings with a number of 1's that is 2 mod 3, was more complicated but the concept was similar. The question gave us the state invariant that was (q0, q'0)=an even number of zero's and a number of 1's such that 0 mod 3, using the two machines and this invariant I found that the other invariants were:
(q0, q'1)=an even number of zero's and a number of 1's such that 1 mod 3,
(q0, q'2)=an even number of zero's and a number of 1's such that 2 mod 3,
(q1, q'0)=an odd number of zero's and a number of 1's such that 0 mod 3,
(q1, q'1)=an odd number of zero's and a number of 1's such that 1 mod 3,
(q1, q'2)=an odd number of zero's and a number of 1's such that 2 mod 3,

For the second part of the question, I used the previous states to determine the state the extended transition would lead to. For example the state
d*(S,100100) has an even number of 0's and 2 1's, which when divided by 3 has remainder 2. Thus it is in state q0,q'2.

Conclusion: Overall I found that I was able to effectively apply my past experiences from assignment 3 to help me with this question. I was satisfied with the way I solved this problem and I think my method was the most efficient way to approach the problem.

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.

Program correctness

This week, the focus of you lectures have moved towards program correctness, which is more or less a formalization of proving that your code does what it should. I found this topic to actually be quite intuitive and something I had been doing in a much less rigorous and formal way in my head when planning my code. I also know have more of an appreciation for the somewhat draconionan rules we had for program style, most of which was directed towards making your code both readable and breaking it up into smaller parts. The idea of smaller blocks of code with helper function especially seems useful now since trying assess the correctness of a large block of text is far more daunting then the same code broken up into several parts. However, applying the proof methods we've learned to program correctness feels infinitely more tedious, with the attention to detail required being astronomically greater. I can't imagine how development teams would manage to be able to prove their code correct for a major project like an operating system. Unfortunately suspect that they don't, though I also suspect our computers would benefit greatly if the did.

Recursion and Unwinding

Having seemingly finished induction for now, though it will inveitably come up again I'm sure, we've know moved the focus of our lecture towards recursions and time complexity. Recursion was initially a bit of an odd concept to me in programing class. While I didn't have any exceptional difficulty understanding it and it's usefulness, it always seemed much more natural to accomplish the same goal with a series of While loops. However, after enough practice, I began to become more use to the idea of using recursions consistently, if for nothing else because of how it seemed to form a far more elegant solution to most problems. However, after finding closed forms for recursively defined functions in lecture, recursion seems far less elegant. It is somewhat suprising how we define closed forms for recursive functions, as the methods in many ways are rather unintuitive. 

After working on the weeks problem set, and getting stuck at a paticular step, I began to wonder how one would go about proving a closed form could not be found for a function. I would imagine that it's more likely that there are many functions for which we have not yet found the closed form for, rather then we know it is impossible to find a closed form and I for one believe the distinction is important. However, having tried to prove for myself that a function could not have a closed form, and, with Google yielding no useful results, I began to realize a certain failing in my knowledge of proving techniques. For most of the proofs we've done, i've had atleast some idea of the concepts and theorems behind what is necessary to provide insight into what we are proving. Yet, while proving that postage of 5 and 11 cents couldn't make postage of 19 seems black and white, proving that a function couldn't have a closed form is far less intuitive, almost to the point where it feels like i'm trying to prove a cat isn't a dog without knowing what a dog is.

The first term test

In general, I have found most university tests and exams to be soul crushing affairs that, taken collectively over the span of the year, constitutes a suite of hostile, spiteful acts against the test taker and humanity itself. Thus, this year I resolved to stay at least a week ahead of all my assignments and tests where possible and afford my self as much time possible. Surprisingly, the spread of quantifiable difference it has made between courses affords an incredible range of results, some much more positive then others.

I am pleased with how the first test went and found it it to be both fair and meaningful assesment of our ability to demonstrate and apply the knowledge we've learned in the class and am glad to see that my studying and effort thus far have paid off, both in terms of my confidence with material and with my enthusiam towards the course. 

The benefit of weekly problem sets

With the start of second year, I have noticed many changes in the format of the assignments and weekly work in my csc courses. Having had to submit weekly problem sets for mat137y1 in first year and with the memory of the countless hours poured into the questionably difficult proofs, I was dreading the idea of having to do the same for csc236, csc207 and the required computational statistics. However, I was suprised to see the difference that keeping ontop of the weekly exercises for csc236 seemed to make in my ability to complete the first assignment. Ultimately, I think the reason I find the problem sets this year more useful then the ones from my math courses last year is because the difficulty is enough that I need to look over the notes i've made in class, but not so difficult that I become hopelessly lost and am forced to create a large study group to solve them. I found that the most useful aspect of these weekly problem sets are their ability to get me to review the material covered in class since, in first year, I found it incredibly difficult to do as the due dates and test dates of all the courses I had seemed to fall in the same week and left me with little time outside of working on them. 

While the weekly assignments mean I have more work to do each week, it seems to lower the overall amount I need to revise before assignments and tests, since the concepts and materials have had a longer time to processed. Additionally I find it much easier to learn the concepts when the revision is done closer to when the exercise was done in class and because i'm not forced to recall a large number of distant concepts in one or two large chunks of time. Although my former first year self would be disgusted by the thought, this year i'm finding the problem sets this year to be extremely useful and effective tool towards learning the material, rather then a weekly chore.

Beginning csc236

For the fall semester, we have just begun csc236, the follow up course to csc165. Having done csc165 in the fall semester of the previous year, I'm finding that my induction skills are a bit rusty. However, having taken a large number of math courses in the meantime, I'm finding myself able to remember the techniques of induction quiet quickly. I'm finding the problem sets to be a good way of keeping myself up to date with the material and am trying to keep at least a few days ahead of each of my due dates for all of my courses. Thus far, it seems to greatly reduce the stress of university life.