Since this is the end of term, I've decided to reflect on the course. I came out of csc165 enthusiastic about computer logic. Gladly, csc236 has not wane my enthusiasm. If it wasn't for the pervasiveness of some personal problems, I believe that I would have been doing better in this course. However, it was still my enthusiasm for computer logic that kept me on top of my studies (whereas in my other courses... not so good).
So some things demystified : proof with induction (iteration, recursion), proof of program correctness and formal languages. This course has shaped how I see proofs. It seems to me that almost everything can be proven with induction. Formal languages is proving strings. I can sort of see how this can be applied to computers (regex and DFSA). The variability of CGFs, along with a stochastic model (markov chain?) seems to be a good starting point for recreating human language, hence could be some sort of AI algorithm. I will probably investigate this further during the winter break.
I enjoyed csc236 and Danny as my prof. Hopefully I will see him again in other computer courses I am going to take. :)
Friday, December 5, 2008
Polya's problem
This was taken out of the CFG problems section of the textbook.
Problem : Prove that the following CDF generates the set of strings over {0.1} that have equally many 0s and 1s.
S -> 0S1S
S -> 1S0S
s -> E
1. Understanding the Problem:
We need to prove that the CDF gives a string with equal number of 1s and 0s.
2. Devise a Plan:
I'll probably have to use three cases, one for 0S1S, 1S0S and E. I'll also need to use induction (simple)
3. Carrying out the plan:
Base Case: If S -> E, then there are no 0s or 1s. That means that there are equal numbers of 1s and 0s.
Inductive Step: Assume that S is of equal number of 1s and 0s by IH.
Case 1S0S: Let the string be 1S0S. By IH, S has equal number of 1s and 0s. Adding another 1 and 0 will end up with equal number of 1s and 0s. Therefore, this case produces the same number of 1s and 0s.
Case 0S1S: Let the string be 0S1S. By IH, S has equal number of 1s and 0s. Adding another 1 and 0 will end up with equal number of 1s and 0s. Therefore, this case produces the same number of 1s and 0s.
By all cases listed above, this CDF produces the same number of 1s and 0s.
4. Looking Back:
I think this result makes sense. There lacks a structure, but the logic is still retained.
Problem : Prove that the following CDF generates the set of strings over {0.1} that have equally many 0s and 1s.
S -> 0S1S
S -> 1S0S
s -> E
1. Understanding the Problem:
We need to prove that the CDF gives a string with equal number of 1s and 0s.
2. Devise a Plan:
I'll probably have to use three cases, one for 0S1S, 1S0S and E. I'll also need to use induction (simple)
3. Carrying out the plan:
Base Case: If S -> E, then there are no 0s or 1s. That means that there are equal numbers of 1s and 0s.
Inductive Step: Assume that S is of equal number of 1s and 0s by IH.
Case 1S0S: Let the string be 1S0S. By IH, S has equal number of 1s and 0s. Adding another 1 and 0 will end up with equal number of 1s and 0s. Therefore, this case produces the same number of 1s and 0s.
Case 0S1S: Let the string be 0S1S. By IH, S has equal number of 1s and 0s. Adding another 1 and 0 will end up with equal number of 1s and 0s. Therefore, this case produces the same number of 1s and 0s.
By all cases listed above, this CDF produces the same number of 1s and 0s.
4. Looking Back:
I think this result makes sense. There lacks a structure, but the logic is still retained.
Subscribe to:
Comments (Atom)