Question. Consider the language L, consisting of strings over the alphabet /sigma = {0,1}; that have an even number of 1s. For each of the regular expressions below, either prove they denote L, or else nd a counter-example that shows they do not. Your counter-example should either exhibit a string that is inL but not denoted by the regular expression, or else one denoted by the regular expression that is not in L.
To give out a counter example is easy, so here I will not show that part.
(b) R2 = (0 + (10*1))*
R_2 does denote L.
UNDERSTANDING THE PROBLEM
To prove a regular expression denotes a language, we need to show that
R2 is a subset of L and L is a subset of R2. Here we can use structural
induction.
DEVISING A PLAN
1) Prove that R2 is a subset of L
2) Prove that L is a subset of R2
CARRYING OUT THE PLAN
Let L be the set of binary strings that have even number of 1s.
Then the regular expression R_2 = (0 + (10*1))* denotes L.
Claim: for any string x, x is in L if and only if x is in L(R_2)
1)
Proof.[IF] Let x be an arbitrary string in language L,
then x contains even number of 1s, say 2n for some natural number n.
Then x can be decomposed as the concatenation of X_1 through X_k
where X_i (1 <= i <= k) = substring with even number of 1s.
To have even 1s, and for small unit, X_i has either zero 1 or two 1s.
Then x can be formed as below:
x = (0 + (1(0...0)1))(0 + (1(0...0)1))......(0 + (1(0...0)1))
X_1 X_1 X_k
There might me one or more zeros between two 1s, thus we use (10*1)
to denote the substring with two 1s.
Then each X_i is in the language (0 + (10*1)), 1 <= i <= k.
So x is in the language L((0 + (10*1))^k) which is a subset of
L((0 + (10*1))*). Thus language L is a subset of L((0 + (10*1))*).
2)
[ONLY IF] Let x be an arbitrary string in L((0 + (10*1))*).
Then there is some natural number k, and y_0, y_1, ..., y_k in /sigma *
such that y_i is in L(0 + (10*1)), for all i such that 0 <= i <= k.
Therefore there are natural numbers m_1, m_2,...,m_k such that
y_i = 0 + 1(0^(m_i))1, for all i such that 0 <= i <= k.
Obviously, y_i is either 0 or 1(0^(m_i))1,
So y_i either has no 1 or two 1s.
Let a,b be two natural numbers where a + b = (k - 0 ) + 1 = k + 1.
Assume there are "a" substrings y_i that is 0, and "b" substrings
y_i that has two 1s. Then the total number of 1s is
0*a + 2*b = 2b, which is even. Thus x is in language L, as wanted.
Since every string in L(R_2) is in language L, and every string in
L is in L(R_2), R_2 denotes L.
Look Back
This episode can be used to prove most of the questions about
proving the regular expression R denotes L.
2008年12月5日星期五
Problem Episode on proving the program is correct
Question.
Prove that if quotRem(n,m) is called with arguments that satisfy the precondition, it terminates, and
when it does it satises the postcondition.
def quotRem(n,m) :
# Precondition: n,m are natural numbers
# m is not 0
r = n
q = 0
while (not (m > r)) :
r = r - m
q = q + 1
# Postcondition: n = qm + r and 0 <= r < m
return [q, r]
UNDERSTANDING THE PROBLEM
Given a program with a while loop. We need to prove that the program
acturally terninates and the precondition implies the postcondition.
For each while loop, r decreases by m, and q increment by 1. Since the
loop condition is on r, which is a decreasing natural number, thus the
while loop will terninate. We will show the correctness of the program by
proving using induction.
DEVISING A PLAN
1) Prove that for each loop, the loop invariant is correct.
2) Prove the while loop acturally terminates.
This proof need 2 steps: 1st is to prove that the loop invariant is in a strictly
decreasing sequence. Then by PWO , we show that the loop terminates.
3) Prove that the precondition implies the postcondition. This step is simple,
since we have shown most of the needed condition in 1) and 2).
CARRYING OUT THE PLAN
1)
Let P(i) be if there is i iterations, if the precondition is true,
then n = q_i * m + r_i and 0 <= r_i < m is a natural number.
Claim 1a: for all natural number i, P(i).
Proof.
Base case: If i = 0, then r_0 = n by line 1 and q_0 = 0 by line 2.
So n = 0 + n = q_0 + r_0. Since the loop does not execute,(0 iteration)
it's obvious that the condition (not m > r) fails,
so m is greater than r_0. Since r_0 = n is a natural number by precondition,
r_0 >= 0. So we have 0 <= r_0 < m. So P(0) is true.
Induction step: Assume that P(i) is true for any natural number i.
We need to show that P(i+1) is true.
If there is no (i+1)th iteration of the loop, P(i) is vacuously true.
Otherwise, assume there is (i+1)th iteration and precondition holds.
r_(i+1) = r_i - m by line 4, q_(i+1) = q_i + 1.
n = q_i * m + r_i (by IH) = q_i * m + r_i + m - m
= m *(q_i + 1) + (r_i - m)
= m * (q_(i+1)) + r_(i+1)
Hence P(i+1) is true.
We have shown that P(i) implies P(i+1) for any natural number i,
So we have P(i) for any natural number i.
2)
Claim 1b: Let E_i = r_i - m be a natural number. If m <= n,
m is a positive natural number, then E_i is a strictly decreasing sequence.
Proof: Base case: if m = n, then E_0 = n - m = 0. E_1 = r_1 - m = 0 - m < 0.
E_1 is not a natural number, so the set E_i only contains 0, we can
say that this is a strictly decreasing sequence.
Induction step: if m < n, and there is (i+1) iterations,
then r_(i+1) = r_i - m. We have
E_(i+1) = r_(i+1) - m = (r_i - m) - m = r_i - 2m.
By precondition, we know that m is not equal to 0 and m is a natural number.
So m > 0, and r_i - 2m < r_i - m, which implies E_(i+1) < E_i. Thus E is a
strictly decreasing sequence.
Hence E_i is a strictly decreasing sequence.
Claim 1c: quotRem(n,m) terminates.
Proof: n,m are natural numbers. If m > n, then we are done since the loop will
not execute and so will terminate. Otherwise, m <= n, the the loop will execute.
We have shown that natural number E_i = r_i - m is a strictly decreasing sequance
and non-empty since it contains at least E_0 = r_i - m = n - m >= 0.
Then by Principle of Well Ordering, there is a least value, say E_k, which must
also be last (strictly decreasing), which means there is no (k + 1)th iteration
of the loop. Thus the loop terminates.
3)
Claim 1d: If precondition is true, then the postcondition is true.
Proof. We have shown that the precondition implies that the loop terminates and
for each loop n = q_i * m + r_i and 0 <= r_i < m.
Thus for the last loop n = q_k * m + r_k and 0 <= r_i < m, and the loop
terminates. Write this form without indicating the subscript, we have
n = q*m + r and 0 <= r < m, satisfying the postcondition.
Therefore, the precondition implies the postcondition.
Looking Back
This episode can be used to prove most of the question on correctness of the program.
Prove that if quotRem(n,m) is called with arguments that satisfy the precondition, it terminates, and
when it does it satises the postcondition.
def quotRem(n,m) :
# Precondition: n,m are natural numbers
# m is not 0
r = n
q = 0
while (not (m > r)) :
r = r - m
q = q + 1
# Postcondition: n = qm + r and 0 <= r < m
return [q, r]
UNDERSTANDING THE PROBLEM
Given a program with a while loop. We need to prove that the program
acturally terninates and the precondition implies the postcondition.
For each while loop, r decreases by m, and q increment by 1. Since the
loop condition is on r, which is a decreasing natural number, thus the
while loop will terninate. We will show the correctness of the program by
proving using induction.
DEVISING A PLAN
1) Prove that for each loop, the loop invariant is correct.
2) Prove the while loop acturally terminates.
This proof need 2 steps: 1st is to prove that the loop invariant is in a strictly
decreasing sequence. Then by PWO , we show that the loop terminates.
3) Prove that the precondition implies the postcondition. This step is simple,
since we have shown most of the needed condition in 1) and 2).
CARRYING OUT THE PLAN
1)
Let P(i) be if there is i iterations, if the precondition is true,
then n = q_i * m + r_i and 0 <= r_i < m is a natural number.
Claim 1a: for all natural number i, P(i).
Proof.
Base case: If i = 0, then r_0 = n by line 1 and q_0 = 0 by line 2.
So n = 0 + n = q_0 + r_0. Since the loop does not execute,(0 iteration)
it's obvious that the condition (not m > r) fails,
so m is greater than r_0. Since r_0 = n is a natural number by precondition,
r_0 >= 0. So we have 0 <= r_0 < m. So P(0) is true.
Induction step: Assume that P(i) is true for any natural number i.
We need to show that P(i+1) is true.
If there is no (i+1)th iteration of the loop, P(i) is vacuously true.
Otherwise, assume there is (i+1)th iteration and precondition holds.
r_(i+1) = r_i - m by line 4, q_(i+1) = q_i + 1.
n = q_i * m + r_i (by IH) = q_i * m + r_i + m - m
= m *(q_i + 1) + (r_i - m)
= m * (q_(i+1)) + r_(i+1)
Hence P(i+1) is true.
We have shown that P(i) implies P(i+1) for any natural number i,
So we have P(i) for any natural number i.
2)
Claim 1b: Let E_i = r_i - m be a natural number. If m <= n,
m is a positive natural number, then E_i is a strictly decreasing sequence.
Proof: Base case: if m = n, then E_0 = n - m = 0. E_1 = r_1 - m = 0 - m < 0.
E_1 is not a natural number, so the set E_i only contains 0, we can
say that this is a strictly decreasing sequence.
Induction step: if m < n, and there is (i+1) iterations,
then r_(i+1) = r_i - m. We have
E_(i+1) = r_(i+1) - m = (r_i - m) - m = r_i - 2m.
By precondition, we know that m is not equal to 0 and m is a natural number.
So m > 0, and r_i - 2m < r_i - m, which implies E_(i+1) < E_i. Thus E is a
strictly decreasing sequence.
Hence E_i is a strictly decreasing sequence.
Claim 1c: quotRem(n,m) terminates.
Proof: n,m are natural numbers. If m > n, then we are done since the loop will
not execute and so will terminate. Otherwise, m <= n, the the loop will execute.
We have shown that natural number E_i = r_i - m is a strictly decreasing sequance
and non-empty since it contains at least E_0 = r_i - m = n - m >= 0.
Then by Principle of Well Ordering, there is a least value, say E_k, which must
also be last (strictly decreasing), which means there is no (k + 1)th iteration
of the loop. Thus the loop terminates.
3)
Claim 1d: If precondition is true, then the postcondition is true.
Proof. We have shown that the precondition implies that the loop terminates and
for each loop n = q_i * m + r_i and 0 <= r_i < m.
Thus for the last loop n = q_k * m + r_k and 0 <= r_i < m, and the loop
terminates. Write this form without indicating the subscript, we have
n = q*m + r and 0 <= r < m, satisfying the postcondition.
Therefore, the precondition implies the postcondition.
Looking Back
This episode can be used to prove most of the question on correctness of the program.
Problem Episode on tenary tree
Dene the set of ternary trees, T3, as:
(a) The empty tree, /\, is an element of T3.
(b) If trees TL; TM; TR are elements of T3 having no nodes in common, and R is a node that is not in
TL; TM or TR, then T = (R; TL; TM; TR) is an element of T3. We call TL the left subtree, TM the
middle subtree, and TR the right subtree, of T.
Consider two trees equivalent if (a) they are both /\ (the empty tree), or (b) they have equivalent left
subtrees, equivalent middle subtrees, and equivalent right subtrees. So there is one ternary tree with
zero nodes: /\, and one ternary tree with one node: (R;/\;/\; /\). For arbitrary natural number n, nd
a (possibly recursive) formula for the number of non-equivalent ternary trees with n nodes. Prove your
formula is correct.
Artist's impression of the three non-equivalent ternary trees with two nodes.
1.UNDERSTANDING THE PROBLEM
Given the definition of a tenary tree with 3 nodes. We need to generize a (possibly recursive) formula for the number of non-equivalent ternary trees with n nodes. Then we need to prove it.
2.DEVISING A PLAN
1, Analyze the tenary tree by trying some small number of nodes.
2, Generate a formula for the number of nodes of the tenary tree.
3, Prove the formula is correct by induction.
CARRYING OUT THE PLAN
1)Analysis:
Notice that if we separately analyzes the ways a tree displayed with n nodes,
we can show it as a sum of all possible ways.
Let's take 3 nodes for example. let the possible ways be G(n)
Then, case1, if the left subtree has 0 nodes
case 1a, if the middle subtree has 0 nodes,
the right subtree has 2 nodes. G(n) = G(0)*G(0)*G(2)
case 1b, if the middle subtree has 1 nodes,
the right subtree has 1 nodes. G(n) = G(0)*G(1)*G(1)
case 1c, if the middle subtree has 2 nodes,
the right subtree has 0 nodes. G(n) = G(0)*G(2)*G(0)
Symmetrically, case2 will be when left subtree has 1 nodes and case3 will be
when left subtree has 2 nodes.
Then the total way of displaying is
G(n) = G(0)*G(0)*G(2) + G(0)*G(1)*G(1) + G(0)*G(2)*G(0) + G(1)*G(0)*G(1) +
G(1)*G(1)*G(0) + G(2)*G(0)*G(0) = 3 + 1 + 3 + 1 + 1 + 3 = 12
2) So, the close form
G(n) = 1, if n < i="0}^(n-1)" j="0}^(n-1-i)">= 2
3)
let P(n) be "There are G(n) non-equivalent ternary trees with n nodes."
claim: for all natural number n , P(n)
Proof.
Base case: if n = 0, then there is only one way to display the ternary tree.
Hence P(0) is true.
if n = 1, then there is still one way to display the ternary tree by
putting this nodes on the root. Hence P(1) is also true.
Induction step: Assume for any arbitrary natural number n,
P(2),P(3),...,P(n-1) are true. We need to prove that P(n) is true.
case 1. if n <>= 2, then by Induction Hypothesis, G(i), G(j), and G(n-1-i-j)
are all true, 0 <= i <= n-1, 0 <= j <= n-1-i. Notice that if we separately analyzes the ways a tree displayed with n nodes, we can show it as a sum of all possible ways. When there are n-1 nodes, we assume n-1 cases where the left subtree contains {0,1,...,n-2} nodes(exclude root). Then for each of these case, we analyze how many ways a tree can be displayed when the middle subtree contains {0,1,..,n-2}nodes. In specific, we determine, when there are i nodes in left subtree and j nodes in middle subtree, how many ways the ternary tree can be displayed. Notice that when there are i nodes in left subtree, there are maximum (n-1)-i-1(exclude root) nodes in middle subtree and the right subtree will have (n-1)-1-i-j nodes. We know when calculating possible ways, we multiply each possible case together. In this situation, G((n-1)') = G(i)*G(j)*G((n-1)-1-i-j). We add all possible G(n')s and we get G(n-1) = \sum_{i=0}^(n-2) (\sum_{j=0}^((n-1)-i-1) G(i)*G(j)*G((n-1)-1-i-j) ). Now, we assume there are n nodes, Then, similar to G(n-1), there will be n cases, where the left subtree has {0,1,...,n-1} nodes. and the middle subtree may contains {0,1,..,n-1}nodes. when left subtree has i nodes, the middle subtree will maximum has n-1-i nodes and the right subtree will have n-1-i-j nodes. We have each little case with G(n') = G(i)*G(j)*G(n-1-i-j) We add all possible G(n')s and we get G(n) = \sum_{i=0}^(n-1) (\sum_{j=0}^(n-1-i) G(i)*G(j)*G(n-1-j)) Hence P(n) is true. We have shown that for any natural number n >= 2,
P(n-1) implies P(n).
Thus, for any natural number n >= 2, P(n).
Consider both cases, we now have shown that P(n), for any natrual number n.
4, Looking Back
Usually we can use this episode to generate the number of nodes on a tree with n children.
Even though it is somehow complecate than a simple induction proof.
(a) The empty tree, /\, is an element of T3.
(b) If trees TL; TM; TR are elements of T3 having no nodes in common, and R is a node that is not in
TL; TM or TR, then T = (R; TL; TM; TR) is an element of T3. We call TL the left subtree, TM the
middle subtree, and TR the right subtree, of T.
Consider two trees equivalent if (a) they are both /\ (the empty tree), or (b) they have equivalent left
subtrees, equivalent middle subtrees, and equivalent right subtrees. So there is one ternary tree with
zero nodes: /\, and one ternary tree with one node: (R;/\;/\; /\). For arbitrary natural number n, nd
a (possibly recursive) formula for the number of non-equivalent ternary trees with n nodes. Prove your
formula is correct.
Artist's impression of the three non-equivalent ternary trees with two nodes.
1.UNDERSTANDING THE PROBLEM
Given the definition of a tenary tree with 3 nodes. We need to generize a (possibly recursive) formula for the number of non-equivalent ternary trees with n nodes. Then we need to prove it.
2.DEVISING A PLAN
1, Analyze the tenary tree by trying some small number of nodes.
2, Generate a formula for the number of nodes of the tenary tree.
3, Prove the formula is correct by induction.
CARRYING OUT THE PLAN
1)Analysis:
Notice that if we separately analyzes the ways a tree displayed with n nodes,
we can show it as a sum of all possible ways.
Let's take 3 nodes for example. let the possible ways be G(n)
Then, case1, if the left subtree has 0 nodes
case 1a, if the middle subtree has 0 nodes,
the right subtree has 2 nodes. G(n) = G(0)*G(0)*G(2)
case 1b, if the middle subtree has 1 nodes,
the right subtree has 1 nodes. G(n) = G(0)*G(1)*G(1)
case 1c, if the middle subtree has 2 nodes,
the right subtree has 0 nodes. G(n) = G(0)*G(2)*G(0)
Symmetrically, case2 will be when left subtree has 1 nodes and case3 will be
when left subtree has 2 nodes.
Then the total way of displaying is
G(n) = G(0)*G(0)*G(2) + G(0)*G(1)*G(1) + G(0)*G(2)*G(0) + G(1)*G(0)*G(1) +
G(1)*G(1)*G(0) + G(2)*G(0)*G(0) = 3 + 1 + 3 + 1 + 1 + 3 = 12
2) So, the close form
G(n) = 1, if n < i="0}^(n-1)" j="0}^(n-1-i)">= 2
3)
let P(n) be "There are G(n) non-equivalent ternary trees with n nodes."
claim: for all natural number n , P(n)
Proof.
Base case: if n = 0, then there is only one way to display the ternary tree.
Hence P(0) is true.
if n = 1, then there is still one way to display the ternary tree by
putting this nodes on the root. Hence P(1) is also true.
Induction step: Assume for any arbitrary natural number n,
P(2),P(3),...,P(n-1) are true. We need to prove that P(n) is true.
case 1. if n <>= 2, then by Induction Hypothesis, G(i), G(j), and G(n-1-i-j)
are all true, 0 <= i <= n-1, 0 <= j <= n-1-i. Notice that if we separately analyzes the ways a tree displayed with n nodes, we can show it as a sum of all possible ways. When there are n-1 nodes, we assume n-1 cases where the left subtree contains {0,1,...,n-2} nodes(exclude root). Then for each of these case, we analyze how many ways a tree can be displayed when the middle subtree contains {0,1,..,n-2}nodes. In specific, we determine, when there are i nodes in left subtree and j nodes in middle subtree, how many ways the ternary tree can be displayed. Notice that when there are i nodes in left subtree, there are maximum (n-1)-i-1(exclude root) nodes in middle subtree and the right subtree will have (n-1)-1-i-j nodes. We know when calculating possible ways, we multiply each possible case together. In this situation, G((n-1)') = G(i)*G(j)*G((n-1)-1-i-j). We add all possible G(n')s and we get G(n-1) = \sum_{i=0}^(n-2) (\sum_{j=0}^((n-1)-i-1) G(i)*G(j)*G((n-1)-1-i-j) ). Now, we assume there are n nodes, Then, similar to G(n-1), there will be n cases, where the left subtree has {0,1,...,n-1} nodes. and the middle subtree may contains {0,1,..,n-1}nodes. when left subtree has i nodes, the middle subtree will maximum has n-1-i nodes and the right subtree will have n-1-i-j nodes. We have each little case with G(n') = G(i)*G(j)*G(n-1-i-j) We add all possible G(n')s and we get G(n) = \sum_{i=0}^(n-1) (\sum_{j=0}^(n-1-i) G(i)*G(j)*G(n-1-j)) Hence P(n) is true. We have shown that for any natural number n >= 2,
P(n-1) implies P(n).
Thus, for any natural number n >= 2, P(n).
Consider both cases, we now have shown that P(n), for any natrual number n.
4, Looking Back
Usually we can use this episode to generate the number of nodes on a tree with n children.
Even though it is somehow complecate than a simple induction proof.
2008年12月4日星期四
conclude csc236
csc236 is a good course that improves our ability of proving and thinking.
It has a fair mark destributing and overall average work load.
The lecture is very useful compare to other courses.
Also, I guess doing assignment with partners would be a good option,
but I didn't do so. I feel interacted on the lecture and more excitingly,
the professor can remember our names.
Even though I hadn't met TAs yet since I didn't go to office hours,
I believe they will be very helpful.
Overall, this is a course that's worth taking.
It has a fair mark destributing and overall average work load.
The lecture is very useful compare to other courses.
Also, I guess doing assignment with partners would be a good option,
but I didn't do so. I feel interacted on the lecture and more excitingly,
the professor can remember our names.
Even though I hadn't met TAs yet since I didn't go to office hours,
I believe they will be very helpful.
Overall, this is a course that's worth taking.
Test 3
This test is the one that I don't really know what's going to be on it~ since we didn't have assignment on it and also the problem set is for last week. Structural induction sometimes
seems do not work.
For example, if L(R(ab*)) is the language only contains the string "a" is in L and "abb" is in
L, but the concatenation aabb is not in L which contradicts the assumption. Am I mistaken
anywhere....? I guess so and I will figure it out before the final hopefully.
Also, I'm suspitious that the pumping lemma does not imply sometimes. I didn't come out
a specific example yet, but it has so many conditions on it so that it works.
The final is comming and I hope I have enough time for reviewing.
seems do not work.
For example, if L(R(ab*)) is the language only contains the string "a" is in L and "abb" is in
L, but the concatenation aabb is not in L which contradicts the assumption. Am I mistaken
anywhere....? I guess so and I will figure it out before the final hopefully.
Also, I'm suspitious that the pumping lemma does not imply sometimes. I didn't come out
a specific example yet, but it has so many conditions on it so that it works.
The final is comming and I hope I have enough time for reviewing.
2008年11月29日星期六
near the end of the semester
There are something new for the proof strategy, which is structural proof.
We have proved several statements about binary string with certain properties.
At first I was not comfortable with the idea of binary string and now I find
it easier and it has create a new world for proofs.
Assignment 3 is done and there is only one test left until the final.
This semester is going really fast. However I had a good time with lectures
and fair marking. I would love to take this course even if it's not the program
requirement. I hope we can have some practice test or past tests for the final
to decrease the stress of having 3finals consecutively.
Hope all of us will do fine.
We have proved several statements about binary string with certain properties.
At first I was not comfortable with the idea of binary string and now I find
it easier and it has create a new world for proofs.
Assignment 3 is done and there is only one test left until the final.
This semester is going really fast. However I had a good time with lectures
and fair marking. I would love to take this course even if it's not the program
requirement. I hope we can have some practice test or past tests for the final
to decrease the stress of having 3finals consecutively.
Hope all of us will do fine.
2008年11月21日星期五
we have to learn self study....
I feel strongly that even though we are learning the same knowledge about regular expression in both courses csc207 and csc236, I understand better on csc236 than on csc207.
Hence, I believe instructors and the strategy for teaching matter a lot when it comes to learning new knowledge. As I go from elementary school, middle school, high school and now university, I feel that we have more abilities to learn, but the instructor has less strategies to teach.
Though I don't prefer this situation, I have to admit that this process is necessary to make people learn to self study. No one will teach you forever. It's yourself who learns the knowledge.
CSC236 is one of the course that I can mostly understand during the lecture.
So I recommend this course to all the CS students.....(though it's a program requirment)
Hence, I believe instructors and the strategy for teaching matter a lot when it comes to learning new knowledge. As I go from elementary school, middle school, high school and now university, I feel that we have more abilities to learn, but the instructor has less strategies to teach.
Though I don't prefer this situation, I have to admit that this process is necessary to make people learn to self study. No one will teach you forever. It's yourself who learns the knowledge.
CSC236 is one of the course that I can mostly understand during the lecture.
So I recommend this course to all the CS students.....(though it's a program requirment)
订阅：
博文 (Atom)
