Last week of school! And my last post!
We had out last term test today as well. It was easier than I thought - no questions on contex-free gramma. Hope I did better than my 2nd term test. Study hard and do well in the final exams! Most importantly, enjoy the holiday!
Friday, December 5, 2008
Week 12
The languages and their expressions are getting more and more complex.
I don't quite understand why the language L that has an equal number of 0s and 1s violates the pumping lemma. Say for example, u = 1, v = 01, w = 0 and p = 3, then uv^kw \in L still.
Ah, I know where I got it wrong! The example I gave is just a specially case in L, more generally it doesn't hold. For example u = 01, v = 01, w = 0 and p = 3, then uv^kw not \in L.
I don't quite understand why the language L that has an equal number of 0s and 1s violates the pumping lemma. Say for example, u = 1, v = 01, w = 0 and p = 3, then uv^kw \in L still.
Ah, I know where I got it wrong! The example I gave is just a specially case in L, more generally it doesn't hold. For example u = 01, v = 01, w = 0 and p = 3, then uv^kw not \in L.
Week 11
Try to prove the DFSA we derived for binary strings that include the substring 011 last week.
P(x): = delta*(s, x)
= { q_0, if x is zero-free
= { q_1, if x has a 0 suffix but don't contain 011
= { q_2, if x has a 01 suffix but don't contain 011
= { q_3, if x contains 011.
Claim: if Sigma = { 0, 1}, then \forall string x, P(x).
Proof:
Base Case: For x = epsilon, delta*(q_0, epsilon) = q_0 since x is zero-free. All other cases follow since they all have a false antecedent. So P(x) is true in this case.
Induction Step: assume x' \in Sigma and P(x') is true. Let x = x'a, then x \in Sigma and either a = 0 or a = 1.
Case 1: a = 0. Then delta*(s, x) = delta*(q_0, x'a) = delta(delta*(q_0, x'), 0)
= { delta(q_0, 0), if x' is zero-free
= { delta(q_1, 0), if x' has a 0 suffix but don't contain 011
= { delta(q_2, 0), if x' has a 01 suffix but don't contain 011
= { delta(q_3, 0), if x' contains 011
= { q_1, if x has a 0 suffix but don't contain 011
= { q_1, if x has a 0 suffix but don't contain 011
= { q_1, if x has a 0 suffix but don't contain 011
= { q_3, if x contains 011.
So P(x) is true in Case 1.
Case 2: a = 1. Then delta*(s, x) = delta*(q_0, x'a) = delta(delta*(q_0, x'), 1)
= { delta(q_0, 1), if x' is zero-free
= { delta(q_1, 1), if x' has a 0 suffix but don't contain 011
= { delta(q_2, 1), if x' has a 01 suffix but don't contain 011
= { delta(q_3, 1), if x' contains 011
= { q_0, if x is zero-free
= { q_2, if x has a 01 suffix but don't contain 011
= { q_3, if x contains 011
= { q_3, if x contains 011.
So P(x) is true in Case 2.
Thus P(x) is true.
Therefore, if Sigma = {0, 1}, then \forall string x, P(x).
P(x): = delta*(s, x)
= { q_0, if x is zero-free
= { q_1, if x has a 0 suffix but don't contain 011
= { q_2, if x has a 01 suffix but don't contain 011
= { q_3, if x contains 011.
Claim: if Sigma = { 0, 1}, then \forall string x, P(x).
Proof:
Base Case: For x = epsilon, delta*(q_0, epsilon) = q_0 since x is zero-free. All other cases follow since they all have a false antecedent. So P(x) is true in this case.
Induction Step: assume x' \in Sigma and P(x') is true. Let x = x'a, then x \in Sigma and either a = 0 or a = 1.
Case 1: a = 0. Then delta*(s, x) = delta*(q_0, x'a) = delta(delta*(q_0, x'), 0)
= { delta(q_0, 0), if x' is zero-free
= { delta(q_1, 0), if x' has a 0 suffix but don't contain 011
= { delta(q_2, 0), if x' has a 01 suffix but don't contain 011
= { delta(q_3, 0), if x' contains 011
= { q_1, if x has a 0 suffix but don't contain 011
= { q_1, if x has a 0 suffix but don't contain 011
= { q_1, if x has a 0 suffix but don't contain 011
= { q_3, if x contains 011.
So P(x) is true in Case 1.
Case 2: a = 1. Then delta*(s, x) = delta*(q_0, x'a) = delta(delta*(q_0, x'), 1)
= { delta(q_0, 1), if x' is zero-free
= { delta(q_1, 1), if x' has a 0 suffix but don't contain 011
= { delta(q_2, 1), if x' has a 01 suffix but don't contain 011
= { delta(q_3, 1), if x' contains 011
= { q_0, if x is zero-free
= { q_2, if x has a 01 suffix but don't contain 011
= { q_3, if x contains 011
= { q_3, if x contains 011.
So P(x) is true in Case 2.
Thus P(x) is true.
Therefore, if Sigma = {0, 1}, then \forall string x, P(x).
Week 10
Try to prove L(((0 + 1)(0 + 1))*(0 + 1)) denotes the language of binary strings with odd length.
P(x): if Sigma = {0, 1} and L_1 = { x \in Sigma x has odd length}, then L_1 = L(((0 + 1)(0 + 1))*(0 + 1)).
Claim: \forall x \in Sigma, P(x).
Proof:
(i) assume x \in Sigma and x \in L_1, then x has odd length, say x = 2*k + 1 for some k \in N. Then x can be written as a concatenation of some substrings of x, i.e. x = x_1x_2...x_kx_(k + 1), where
x_i for 1 <= i <= k carries 2 characters either 0 or 1 and 2*k characters in total;
x_(k + 1), the last character of x.
Since x_i \in L((0 + 1)(0 + 1)), x_1x_2...x_k \in L(((0 + 1)(0 + 1))^k), and x_(k + 1) \in L(0 + 1), x = x_1x_2...x_kx_(k + 1) \in L(((0 + 1)(0 + 1))^k)L(0 + 1) = L(((0 + 1)(0 + 1))^k(0 + 1)), which is a subset of L(((0 + 1)(0 + 1))*(0 + 1)). So L_1 is a subset of L(((0 + 1)(0 + 1))*(0 + 1)).
(ii) assume x \in Sigma and x is a typical string in the language denoted by L(((0 + 1)(0 + 1))*(0 + 1)). Then x can be written as a series of strings x_1x_2...x_k where each x_i carries 2 characters either 0 or 1 for some k \in N concatenated with a single character which can be either 0 or 1. Since each x_i has a length of 2, they have a length of 2*k in total. With the single character at the end, x = 2*k + 1 which is an odd number. So L(((0 + 1)(0 + 1))*(0 + 1)) is a subset of L_1.
Since L_1 is a subset of L(((0 + 1)(0 + 1))*(0 + 1)) and L(((0 + 1)(0 + 1))*(0 + 1)) is a subset of L_1, L_1 = L(((0 + 1)(0 + 1))*(0 + 1)) according to the set property.
Thus, \forall x \in Sigma, P(x).
P(x): if Sigma = {0, 1} and L_1 = { x \in Sigma x has odd length}, then L_1 = L(((0 + 1)(0 + 1))*(0 + 1)).
Claim: \forall x \in Sigma, P(x).
Proof:
(i) assume x \in Sigma and x \in L_1, then x has odd length, say x = 2*k + 1 for some k \in N. Then x can be written as a concatenation of some substrings of x, i.e. x = x_1x_2...x_kx_(k + 1), where
x_i for 1 <= i <= k carries 2 characters either 0 or 1 and 2*k characters in total;
x_(k + 1), the last character of x.
Since x_i \in L((0 + 1)(0 + 1)), x_1x_2...x_k \in L(((0 + 1)(0 + 1))^k), and x_(k + 1) \in L(0 + 1), x = x_1x_2...x_kx_(k + 1) \in L(((0 + 1)(0 + 1))^k)L(0 + 1) = L(((0 + 1)(0 + 1))^k(0 + 1)), which is a subset of L(((0 + 1)(0 + 1))*(0 + 1)). So L_1 is a subset of L(((0 + 1)(0 + 1))*(0 + 1)).
(ii) assume x \in Sigma and x is a typical string in the language denoted by L(((0 + 1)(0 + 1))*(0 + 1)). Then x can be written as a series of strings x_1x_2...x_k where each x_i carries 2 characters either 0 or 1 for some k \in N concatenated with a single character which can be either 0 or 1. Since each x_i has a length of 2, they have a length of 2*k in total. With the single character at the end, x = 2*k + 1 which is an odd number. So L(((0 + 1)(0 + 1))*(0 + 1)) is a subset of L_1.
Since L_1 is a subset of L(((0 + 1)(0 + 1))*(0 + 1)) and L(((0 + 1)(0 + 1))*(0 + 1)) is a subset of L_1, L_1 = L(((0 + 1)(0 + 1))*(0 + 1)) according to the set property.
Thus, \forall x \in Sigma, P(x).
Week 9
As what I have expected, term test 2 tested something about the loop invariant. I spent a lot of time on it and didn't finish the proof of termination of the program although that maight only take about one line or two. For the loop invariant part, I didn't think I got that right either, where I put a lot of things - a lot more that what it should be.
However, I think I am kind of getting it now. From what I think, loop invariant should include at least the preconditions of the loop, like the nature of the variables in the loop; the condition of the loop (the part after while or if) for the loop to execute; and the postcondition of the loop written with the subscript i denoting the ith iteration of the loop, for that in the last iteration of the loop, it will just return what the postcondition says. I hope this would work.
Anyways, I didn't do as well in term test 2 as in test 1. I should really investigate more on the loop invariant stuff for that there for sure would be a question on it on the final exam!
However, I think I am kind of getting it now. From what I think, loop invariant should include at least the preconditions of the loop, like the nature of the variables in the loop; the condition of the loop (the part after while or if) for the loop to execute; and the postcondition of the loop written with the subscript i denoting the ith iteration of the loop, for that in the last iteration of the loop, it will just return what the postcondition says. I hope this would work.
Anyways, I didn't do as well in term test 2 as in test 1. I should really investigate more on the loop invariant stuff for that there for sure would be a question on it on the final exam!
Week 8
I am having some troubles stating the loop invariant, like the example we had during Wednesday's (Oct. 29th) lecture. For the function counter, how we worked out its loop invariant to be: a and b \in N, and 7*m + n = 7*a_i + b_i + c_i? I think I know why a and b has to be natural numbers, but for the latter part, the equation, I really didn't get it. Did we use the trail and error, or there is a systematic way for us to find the loop invariant for any while loops and for loops?
I know the casual defination for the loop invariant is that any variable or relationship that is unchanged during the loop's execution. However, will that just be the loop's content itself?
I know the casual defination for the loop invariant is that any variable or relationship that is unchanged during the loop's execution. However, will that just be the loop's content itself?
Week 7
Assignment 2 is so hard!
Although question 1 is from assignment 1, I still didn't get it this time. The only part of this question that I felt confident about is I managed to show that if a ternary tree has n nodes, there will be (2*n + 1) positions available to add a new node onto the tree. Although I didn't include that into my solution to question 1 since I think it is kind of irrelevant to the problem, I will prove it here.
P(n): if a ternary tree has n nodes, there will be (2*n + 1) positions on the tree available to add a new node.
Claim: \forall n \in N, P(n).
Proof: Base Case: For n = 0, the tree is the empty tree and there is only one position available to add a new node, namely the root. Since 1 = 2*0 + 1, P(0) is true.
Induction Step: assume n \in N and P(n) is true, that is (2*n + 1) positions are available to be added for a ternary tree with n nodes. To add a new node, note that it will take up one old position but itself will open up three new positions for a newer node to be add. Thus, from n to (n + 1), 2 more positions are created. Since 2*n + 1 + 2 = 2*(n + 1) + 1, P(n + 1) is true.
So \forall n \in N, P(n) => P(n + 1).
Thus, \forall n \in N, P(n).
That is everything. Hope the next assignment and the coming test won't be that hard.
Although question 1 is from assignment 1, I still didn't get it this time. The only part of this question that I felt confident about is I managed to show that if a ternary tree has n nodes, there will be (2*n + 1) positions available to add a new node onto the tree. Although I didn't include that into my solution to question 1 since I think it is kind of irrelevant to the problem, I will prove it here.
P(n): if a ternary tree has n nodes, there will be (2*n + 1) positions on the tree available to add a new node.
Claim: \forall n \in N, P(n).
Proof: Base Case: For n = 0, the tree is the empty tree and there is only one position available to add a new node, namely the root. Since 1 = 2*0 + 1, P(0) is true.
Induction Step: assume n \in N and P(n) is true, that is (2*n + 1) positions are available to be added for a ternary tree with n nodes. To add a new node, note that it will take up one old position but itself will open up three new positions for a newer node to be add. Thus, from n to (n + 1), 2 more positions are created. Since 2*n + 1 + 2 = 2*(n + 1) + 1, P(n + 1) is true.
So \forall n \in N, P(n) => P(n + 1).
Thus, \forall n \in N, P(n).
That is everything. Hope the next assignment and the coming test won't be that hard.
Week 6
I think the Master Therom for divide and conquer is so complicated. It has a lots of parameters (like a, b l) and conditions (like equal piece division), and the asymptote bounds generated by it is complicated too. Hope we don't have to memorize the whole formula in a test or exam.
One excited stuff: I got perfect on my term test 1! Although term test 1 is more like the stuff we did in CSC165, I am still happy about that, and should study even harder next time to keep the record, I guess.
One excited stuff: I got perfect on my term test 1! Although term test 1 is more like the stuff we did in CSC165, I am still happy about that, and should study even harder next time to keep the record, I guess.
Week 5
In the lecture on Oct 6th, we worked out a closed form for the function:
0, if n = 0
H(n) = { 2, if n = 1
3*H(n - 1) - 2*H(n - 2), if n > 1
which is H(n) = 2^(n + 1) - 2. Here is a proof of this formula by complete induction.
P(n): the closed form for the given function above is H(n) = 2^(n + 1) - 2.
Claim: \forall n \in N, P(n).
Proof: assume n \in N and P(0) /\ P(1) /\.../\P(n - 1) are true. Then either n <= 1 or n > 1.
Case 1: n <= 1. For n = 0, H(0) = 2^(0 + 1) - 2 = 2 - 2 = 0 which satisfies the defination of H(n) when n = 0. For n = 1, H(1) = 2^(1 + 1) - 2 = 4 - 2 = 2 which also satisfies the defination for n = 1. So H(0) and H(1) are true.
Case 2: n >= 1. According to the defination of H(n), H(n) = 3*H(n - 1) - 2*H(n - 2) = 3*(2^(n - 1 + 1) - 2) - 2*(2^(n - 2 + 1) - 2) = 3*2^n - 6 - 2*2^(n - 1) + 4 = 3*2^n - 2^n - 2 = 2*2^n - 2 = 2^(n + 1) - 2 which is the closed form for H(n).
So \forall n \in N, P(0) /\ P(1) /\.../\ P(n - 1) => P(n)
Thus, \forall n \in N, P(n).
0, if n = 0
H(n) = { 2, if n = 1
3*H(n - 1) - 2*H(n - 2), if n > 1
which is H(n) = 2^(n + 1) - 2. Here is a proof of this formula by complete induction.
P(n): the closed form for the given function above is H(n) = 2^(n + 1) - 2.
Claim: \forall n \in N, P(n).
Proof: assume n \in N and P(0) /\ P(1) /\.../\P(n - 1) are true. Then either n <= 1 or n > 1.
Case 1: n <= 1. For n = 0, H(0) = 2^(0 + 1) - 2 = 2 - 2 = 0 which satisfies the defination of H(n) when n = 0. For n = 1, H(1) = 2^(1 + 1) - 2 = 4 - 2 = 2 which also satisfies the defination for n = 1. So H(0) and H(1) are true.
Case 2: n >= 1. According to the defination of H(n), H(n) = 3*H(n - 1) - 2*H(n - 2) = 3*(2^(n - 1 + 1) - 2) - 2*(2^(n - 2 + 1) - 2) = 3*2^n - 6 - 2*2^(n - 1) + 4 = 3*2^n - 2^n - 2 = 2*2^n - 2 = 2^(n + 1) - 2 which is the closed form for H(n).
So \forall n \in N, P(0) /\ P(1) /\.../\ P(n - 1) => P(n)
Thus, \forall n \in N, P(n).
Week 4
I don't quite understand the "Zero-pair free binary strings" example given in class on Oct. 1st. It says:
def zpf(n):
if n == 0: #return the number of empty BS that do not have pairs of adjacent zeros.
if n == 1: #return the number of length one BS that do not have pairs of adjacent zeros.
else: #how many strings of length n, in terms of n - 1 and n - 2?
What does the last sentence mean? Does it mean that the strings of length n equals can be represented by the strings of length (n - 1) and (n - 2)? If so, how?
The example we had in class was:
00 and 10 in terms of n - 2
01 and 11 in terms of n - 1
That's even more confusing. Does it mean that if the string has length n ends with 00 or 10, the number of zero-free pairs equals that has a length (n - 2), and same argument for strings ends with 01 or 11? If so, why this is true?
I guess I'll look through the textbook to see if there is a solution to my question.
def zpf(n):
if n == 0: #return the number of empty BS that do not have pairs of adjacent zeros.
if n == 1: #return the number of length one BS that do not have pairs of adjacent zeros.
else: #how many strings of length n, in terms of n - 1 and n - 2?
What does the last sentence mean? Does it mean that the strings of length n equals can be represented by the strings of length (n - 1) and (n - 2)? If so, how?
The example we had in class was:
00 and 10 in terms of n - 2
01 and 11 in terms of n - 1
That's even more confusing. Does it mean that if the string has length n ends with 00 or 10, the number of zero-free pairs equals that has a length (n - 2), and same argument for strings ends with 01 or 11? If so, why this is true?
I guess I'll look through the textbook to see if there is a solution to my question.
Week 3
I am a little bit behind, but here is the proof of the uniqueness of quotient and remainder Prof. Heap mentioned in last Friday's (Sept 19's) class.
P(m): \forall n \in N\{0}, if \exists q and r \in N such that m = q*n + r and 0 <= r < n, then q and r are unique.
Claim: \forall m \in N, P(m).
Proof (by contradiction): assume m \in N. First we know that by the Principle of Well-Ordering, the set R = {r \in N \exists q \in N, m = q*n + r} has a least element, call it r_1 and the q corresponding to this r_1 is q_1. Then m = q_1*n + r_1. If q_1 and r_1 are unique, then there exist a pair q_2 and r_2 such that m = q_2*n + r_2 and 0 <= r_2 < m =" q_1*n" r_1 =" q_2*n"> r_1. Rearrange the above equation, we get (q_1 - q_2)*n = r_2 - r_1 > 0. So q_1 > q_2. Say q_1 = q_2 + k where k is some natural number greater than 0. Then m = q_1*n + r_1 = (q_2 + k) *n + r_1 = q_2*n + (r_1 + k*n) = q_2*n + r_2. So r_2 = r_1 + k*n > n, contradicts to that 0 <= r_2 < n. So q_1 and r_1 are unique.
So \forall m \in N, P(m).
P(m): \forall n \in N\{0}, if \exists q and r \in N such that m = q*n + r and 0 <= r < n, then q and r are unique.
Claim: \forall m \in N, P(m).
Proof (by contradiction): assume m \in N. First we know that by the Principle of Well-Ordering, the set R = {r \in N \exists q \in N, m = q*n + r} has a least element, call it r_1 and the q corresponding to this r_1 is q_1. Then m = q_1*n + r_1. If q_1 and r_1 are unique, then there exist a pair q_2 and r_2 such that m = q_2*n + r_2 and 0 <= r_2 < m =" q_1*n" r_1 =" q_2*n"> r_1. Rearrange the above equation, we get (q_1 - q_2)*n = r_2 - r_1 > 0. So q_1 > q_2. Say q_1 = q_2 + k where k is some natural number greater than 0. Then m = q_1*n + r_1 = (q_2 + k) *n + r_1 = q_2*n + (r_1 + k*n) = q_2*n + r_2. So r_2 = r_1 + k*n > n, contradicts to that 0 <= r_2 < n. So q_1 and r_1 are unique.
So \forall m \in N, P(m).
Week 2
The postage problem we did in class on Sept 19th used complete induction to prove. Here the same problem is proved by simple induction.
P(n): postage of n cents can be formed with 4- and 5-cent stamps.
Claim: \forall n \in N, n >= 12 => P(n).
Proof:
Base Case: for n = 12, 12-cent postage can be made by using three 4-cent stamps. So P(12) is true.
Induction Step: assume n \in N and n >= 12. Also assume P(n) is true, that is postage of n cents can be made by using 4- and 5-cent stamps. Then either n has at least one 4-cent stamp or n doesn't have any 4-cent postage.
Case 1: n has at least one 4-cent stamp. Then for (n + 1) postage, we can exchange that 4-cent stamp to a 5-cent stamp to get one cent more postage. So P(n + 1) is true in this case.
Case 2: n has no 4-cent stamp. Then n must have at least three 5-cent stamps, since 15 is the next natural number after 12 which is a multiple of 5. To get one more postage, we can simply exchange three 5-cent stamps (15 cents) to four 4-cent stamps (16 cents). So P(n + 1) is also true in this case.
Thus, P(n + 1) is true.
So \forall n \in N, (n >= 12 and P(n) ) => P(n + 1)
Therefore, \forall n \in N, n >= 12 => P(n).
P(n): postage of n cents can be formed with 4- and 5-cent stamps.
Claim: \forall n \in N, n >= 12 => P(n).
Proof:
Base Case: for n = 12, 12-cent postage can be made by using three 4-cent stamps. So P(12) is true.
Induction Step: assume n \in N and n >= 12. Also assume P(n) is true, that is postage of n cents can be made by using 4- and 5-cent stamps. Then either n has at least one 4-cent stamp or n doesn't have any 4-cent postage.
Case 1: n has at least one 4-cent stamp. Then for (n + 1) postage, we can exchange that 4-cent stamp to a 5-cent stamp to get one cent more postage. So P(n + 1) is true in this case.
Case 2: n has no 4-cent stamp. Then n must have at least three 5-cent stamps, since 15 is the next natural number after 12 which is a multiple of 5. To get one more postage, we can simply exchange three 5-cent stamps (15 cents) to four 4-cent stamps (16 cents). So P(n + 1) is also true in this case.
Thus, P(n + 1) is true.
So \forall n \in N, (n >= 12 and P(n) ) => P(n + 1)
Therefore, \forall n \in N, n >= 12 => P(n).
Monday, September 29, 2008
Subscribe to:
Posts (Atom)