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.
Subscribe to:
Posts (Atom)