Friday, December 5, 2008
week 13/ test 3
Just had test 3 this week. Question 1 was ok. Just had to spend time to trace the various states. As for the first part, there was a pattern apparently. Question 2 and question 3 were rather similar to what we did in lectures. I used structural induction for the "infinitely many strings/1,0" question and for proving the equivalence, i used an approach similar to what danny did. Prove that each is a subset of another. Correct? I know i'll lose marks here and there but i hope it's ok. Didn't attend lecture today after the test. Only 1 hour of sleep the previous night studying for T3. CSC236 tests worry the hell out of me everytime.
Tuesday, November 25, 2008
week 12 - A3/ Non-Regular Languages Pumping Lemma
A3 was due this week. For me, it seemed as if i managed to find a counter example for all parts of Q2. It seems like there is at least 1 regex that did not exist in the language. It can't possibly be all false. Don't think A3 will go as well now. And as for the DFSA question, it's a pain to have to type the notations. I didn't even know if my notations are correct of what format the question wanted. How do u draw a picture of the DFSA using .txt? Oh man...i must be missing something here. Pen and paper please!!!
Saturday, November 22, 2008
week 11 - NFSAs, Equivalence
Finally after reading through the notes for DFSA, I've figured out the how the DFSA works and i've also finally understood the example about strings that are multiples of 3 in base 2. Sounds complicated, but actually it's quite easy. But to design a DFSA will require careful thought to ensure nothing is left out.
This week we did NFSAs and equivalence. Proving the DFSA sounds straightforward. Just start with the base case that all portions of the state invariant are true, then go on to use x=x'a, a concatenation of strings, to show that the property is preserved. Structural induction in this case? We have to show that starting from a smaller substring x', we arrive at the same state invariants for x as well.
As for NFSA, i have to read up on that. All that NFSA set of states vs DfSA sets is confusing me. We also did cartesian product. It's like a pair of DFSAs to be combined in to one. It's not all that bad.
BUT for regular expressions, the example for even #of 0s and odd # of digits was not all that clear. After removing q_11, why did the transitions linking q_00 to q_01 and q_01 to q_00 change from 1 to 1+01(11)*10? Since q_11 was only linked to q_00 and q_01, why did the transitions from q_00 to q_01 get affected when it was removed?
This week we did NFSAs and equivalence. Proving the DFSA sounds straightforward. Just start with the base case that all portions of the state invariant are true, then go on to use x=x'a, a concatenation of strings, to show that the property is preserved. Structural induction in this case? We have to show that starting from a smaller substring x', we arrive at the same state invariants for x as well.
As for NFSA, i have to read up on that. All that NFSA set of states vs DfSA sets is confusing me. We also did cartesian product. It's like a pair of DFSAs to be combined in to one. It's not all that bad.
BUT for regular expressions, the example for even #of 0s and odd # of digits was not all that clear. After removing q_11, why did the transitions linking q_00 to q_01 and q_01 to q_00 change from 1 to 1+01(11)*10? Since q_11 was only linked to q_00 and q_01, why did the transitions from q_00 to q_01 get affected when it was removed?
Friday, November 21, 2008
Problem Solving Episode
So here goes my problem solving episode:
Question is Q3 from A3.
Prove that any regular expression that doesn't include a Kleene star denotes a ō¸°€nite language.
1. UNDERSTANDING THE PROBLEM
We are supposed to prove that any regular expression that does not contain a * denotes a finite language. This sounds rather straightforward but it's difficult to put in words. The data we have is a regex and finite language. Condition is that any regex that does not contain a * denotes a finite language. We can easily satisfy the condition by assuming a regex without a *. The unknown is the language that we have to show is finite. Condition should be able to determine the unknown.
2. DEVISING A PLAN
First, a regex can be connected to a language. regex denotes a set of strings, just like a language by definition. So a string is made up of a finite number of symbols. Then the plan is to link the finite number of symbols to a string and this can be linked to a regex and then a language. But is this correct? The post on the bulletin board gave some crucial hints.
Seems like we can use structural induction to carry out this proof. We can start from the basic set and show that it satifies the condition that regexes without * will denote a finite language. Then we can carry on to say that 2 regexes that do not contain * will also denote 2 finite languages.
3. CARRYING OUT THE PLAN
Basis will be to show that a regex without a * will denote a finite language. We can use one symbol to show that it denotes a language with just 1 element. So it will be finite.
Then for the induction step: We can show that if 2 regexes(R,S) denotes 2(L(R),L(S)) languages, then by the IH, it will be finite as well. We shall make use of the properties of languages that L(R+S) = L(R) U L(S) and L(RS) = L(R)L(S). So since L(R)+L(S) and L(R)xL(S) are both finite, then we can conclude that any regex that does not contain * will denote a finite language.
4. Looking Back
By using structural induction, we started from the basic set and showed that it's true. Since by making use of the properties of L, structural induction is a powerful tool to show that L1+L2 contains what the IH showed. So this argument should make some sense. Not too sure if there is another way to solve this problem though.
We might also want to try to use the fact that a string is made up of a finite number of symbols and if we can link that fact to regexes without * and ultimately we might be able to use that to denote a finite language.
This concludes my problem solving episode!
Question is Q3 from A3.
Prove that any regular expression that doesn't include a Kleene star denotes a ō¸°€nite language.
1. UNDERSTANDING THE PROBLEM
We are supposed to prove that any regular expression that does not contain a * denotes a finite language. This sounds rather straightforward but it's difficult to put in words. The data we have is a regex and finite language. Condition is that any regex that does not contain a * denotes a finite language. We can easily satisfy the condition by assuming a regex without a *. The unknown is the language that we have to show is finite. Condition should be able to determine the unknown.
2. DEVISING A PLAN
First, a regex can be connected to a language. regex denotes a set of strings, just like a language by definition. So a string is made up of a finite number of symbols. Then the plan is to link the finite number of symbols to a string and this can be linked to a regex and then a language. But is this correct? The post on the bulletin board gave some crucial hints.
Seems like we can use structural induction to carry out this proof. We can start from the basic set and show that it satifies the condition that regexes without * will denote a finite language. Then we can carry on to say that 2 regexes that do not contain * will also denote 2 finite languages.
3. CARRYING OUT THE PLAN
Basis will be to show that a regex without a * will denote a finite language. We can use one symbol to show that it denotes a language with just 1 element. So it will be finite.
Then for the induction step: We can show that if 2 regexes(R,S) denotes 2(L(R),L(S)) languages, then by the IH, it will be finite as well. We shall make use of the properties of languages that L(R+S) = L(R) U L(S) and L(RS) = L(R)L(S). So since L(R)+L(S) and L(R)xL(S) are both finite, then we can conclude that any regex that does not contain * will denote a finite language.
4. Looking Back
By using structural induction, we started from the basic set and showed that it's true. Since by making use of the properties of L, structural induction is a powerful tool to show that L1+L2 contains what the IH showed. So this argument should make some sense. Not too sure if there is another way to solve this problem though.
We might also want to try to use the fact that a string is made up of a finite number of symbols and if we can link that fact to regexes without * and ultimately we might be able to use that to denote a finite language.
This concludes my problem solving episode!
Friday, November 14, 2008
week 10 -Regexes, FSAs
This week we did DFSA and a little of regex algebra. I wonder how important regex algebra will be in this course. But as for DFSA, I didn't really understand what the state invariant meant. But after i read the course notes and understood it better. It's just like a description and it describes how the system moves from the initial state to another state.
However, i didn't really get what the example with the multiples of 3 in base 2 meant. Shall have to go through the part about the x1 and x0 parts again.
However, i didn't really get what the example with the multiples of 3 in base 2 meant. Shall have to go through the part about the x1 and x0 parts again.
Friday, November 7, 2008
week 9 - Formal Languages
For week 9, we had a term test. I was initially quite worried about the test. Had to revise the material over and over again before the test. It doesn't help if i have to work on Thursdays before lecture. But luckily i had time to go through the material one last time before the test. It turned out that the test was ok. The last question did not work out too well but it was ok. I think i forgot to read the last question properly. But it's work 2 marks so hopefully it will not hurt the overall score too much.
During lecture, we did formal languages. So a set of strings is a language. Strings consist of symbols from an Alphabet. Then a language consists of a set of all possible string over the alphabet. So a language is a subset of the alphabet?
Again, nothing made sense during lecture. Had to re-read the slides after i got home. Something confused me a little. For the equality of languages, the example we did was to prove that L1 = {x has an even number of zeros} and L1 = (1*(01*01)*). For Xi, why is the substring starting at (2i-1)and ends at the (2i+1)th 0? Why 2i? Shall ask Danny when during office hours then.
During lecture, we did formal languages. So a set of strings is a language. Strings consist of symbols from an Alphabet. Then a language consists of a set of all possible string over the alphabet. So a language is a subset of the alphabet?
Again, nothing made sense during lecture. Had to re-read the slides after i got home. Something confused me a little. For the equality of languages, the example we did was to prove that L1 = {x has an even number of zeros} and L1 = (1*(01*01)*). For Xi, why is the substring starting at (2i-1)and ends at the (2i+1)th 0? Why 2i? Shall ask Danny when during office hours then.
Friday, October 31, 2008
week 8- iterative correctness
was quite confused about this week's lecture. Didn't understand the part about 7m+n=7a+b+i. The proof made a little sense to me but i just didn't understand the 1st part. This proof is rather similar to that of the previous week's proof. Just this time we have to count the i-th iteration in as well.
Do we have to make use of PWO at this point? To show that at the next iteration, we will always end up with a smaller variable and it will get smaller and smaller until it reaches 0. Is that how we are supposed to make use to PWO? How to apply PWO in this case?
A2 was a disaster. It took way longer than i expected. So as a result i did not finish it. But come to think of it, it was quite impossible for me to finish it. With 2 midterms on 22 and 23, 207 E3 and a group report due on monday then followed 207 midterm on wednesday, it was quite a challenge to finish my work on time. Just bad bad planning on my part.
I know danny reads our blogs...some help maybe? Haha. But oh well..can't ask for anything since i am responsible for my own work. Just hope to survive this course..........
Do we have to make use of PWO at this point? To show that at the next iteration, we will always end up with a smaller variable and it will get smaller and smaller until it reaches 0. Is that how we are supposed to make use to PWO? How to apply PWO in this case?
A2 was a disaster. It took way longer than i expected. So as a result i did not finish it. But come to think of it, it was quite impossible for me to finish it. With 2 midterms on 22 and 23, 207 E3 and a group report due on monday then followed 207 midterm on wednesday, it was quite a challenge to finish my work on time. Just bad bad planning on my part.
I know danny reads our blogs...some help maybe? Haha. But oh well..can't ask for anything since i am responsible for my own work. Just hope to survive this course..........
Subscribe to:
Posts (Atom)