This is the last week of class. Then we are going to review at home and be ready for the final exam!
CSC236 exam is on Dec.12nd.
To do list before final:
1. Review every lecture notes.
2. Do all the tutorial questions again.
3. Review each quiz and assignment.
4. Do the past exams.
5. Read textbook if there are questions.
6. Go to office hour if needed.
BE READY AND CHEER UP!
2012年12月4日星期二
2012年12月3日星期一
Tutorial 8
One question on the tutorial I found very interesting -- the second question on tutorial 8.
It asked to devise a DFSA that accepts the language of strings over {0,1}, with an odd number of 1s and and even number of 0s. From the DFSA, devise the regular expression that denotes the same language.
So first of all, devise a DFSA that has four states. i.e. keep every states and find the relationship between.
Then remove one state at a time and modify all the states that have a relationship with this removed state.
Remove states until there are only two states left: the beginning state and the accepting state.
Finally, use a singe letter to represent a string and write out the regular expression.
This is how I did this problem.
A binary can have an even number of 1s and even number of 0s (EE), or an even number of 1s and an odd number of 0s (EO), or an odd number of 1s and an even number of 0s (OE), or an odd number of 1s and an odd number of 0s (OO). So there are four states : q1, q2, q3,q4 repectively.
The beginning state should an empty string. In this case, there should be no 0s or 1s in this string, so the number of 1s and 0s are both even (there is zero 0 and zero 1). This is in the first state.
The accepting state should by a string that has an odd number of 1s and an even number of 0s. i.e. the third state.
There are two choices to add to the first state: 1 or 0.
If add a 0 to the beginning state, there will be one 0 and zero 1, so there will be an even number of 1s and an odd number of 0s. This is in the second state.
If add a 1 to the beginning state, there will be one 1s and zero 0s, so there will be an odd number of 1s and an even number of 0s. This is in the third state.
Similarly, there are two choices to add to the second state.
The second state has an even number of 1 and an odd number of 0, so if add a 0 to the second state, there will be an even number of 1s and an even number of 0s. This goes back to the first state.
If add a 1 to the second state, there will be an odd number of 1s and an odd number of 0s. This is in the fourth state.
Then let's talk about the third state.
The third state has an odd number of 1s and an even number of 0s. If add a 0 to the third state, there will be an odd number of 1s and an odd number of 0s. This goes to the fourth state.
If add a 1 to the third state, there will be an even number of 1s and even number of 0s. This will go back to the first state.
Same to the fourth state.
The fourth state has an odd number of 1s and an odd number of 0s. If add a 0 to the fourth state, there will be an odd number of 1s and even number of 0s. This goes to the third state.
If add a 1 to the fourth state, there will be an even number of 1s and an odd number of 0s. This goes to the second state.
Once the string goes back to the first state, whatever the next string is 1 or 0, it always going to loop in between these four states.
The graph is as below:
It asked to devise a DFSA that accepts the language of strings over {0,1}, with an odd number of 1s and and even number of 0s. From the DFSA, devise the regular expression that denotes the same language.
So first of all, devise a DFSA that has four states. i.e. keep every states and find the relationship between.
Then remove one state at a time and modify all the states that have a relationship with this removed state.
Remove states until there are only two states left: the beginning state and the accepting state.
Finally, use a singe letter to represent a string and write out the regular expression.
This is how I did this problem.
A binary can have an even number of 1s and even number of 0s (EE), or an even number of 1s and an odd number of 0s (EO), or an odd number of 1s and an even number of 0s (OE), or an odd number of 1s and an odd number of 0s (OO). So there are four states : q1, q2, q3,q4 repectively.
The beginning state should an empty string. In this case, there should be no 0s or 1s in this string, so the number of 1s and 0s are both even (there is zero 0 and zero 1). This is in the first state.
The accepting state should by a string that has an odd number of 1s and an even number of 0s. i.e. the third state.
There are two choices to add to the first state: 1 or 0.
If add a 0 to the beginning state, there will be one 0 and zero 1, so there will be an even number of 1s and an odd number of 0s. This is in the second state.
If add a 1 to the beginning state, there will be one 1s and zero 0s, so there will be an odd number of 1s and an even number of 0s. This is in the third state.
Similarly, there are two choices to add to the second state.
The second state has an even number of 1 and an odd number of 0, so if add a 0 to the second state, there will be an even number of 1s and an even number of 0s. This goes back to the first state.
If add a 1 to the second state, there will be an odd number of 1s and an odd number of 0s. This is in the fourth state.
Then let's talk about the third state.
The third state has an odd number of 1s and an even number of 0s. If add a 0 to the third state, there will be an odd number of 1s and an odd number of 0s. This goes to the fourth state.
If add a 1 to the third state, there will be an even number of 1s and even number of 0s. This will go back to the first state.
Same to the fourth state.
The fourth state has an odd number of 1s and an odd number of 0s. If add a 0 to the fourth state, there will be an odd number of 1s and even number of 0s. This goes to the third state.
If add a 1 to the fourth state, there will be an even number of 1s and an odd number of 0s. This goes to the second state.
Once the string goes back to the first state, whatever the next string is 1 or 0, it always going to loop in between these four states.
The graph is as below:
First remove the fourth state of the device. i.e. remove OO state.
So we can get from EO to OE by adding a 10 and get from OE to EO by adding a 01.
Adding 11 to EO, we are still in state EO and adding 00, we are still in state OE.
Similarly, we can remove one more state, EO.
Then we represent each string by a unique letter: R represents 0(11)*0, P represents 1 + 0(11)*10, Q represents 00 + 01(11)*10 and T represents 1 + 01(11)*10.
There are two ways to get from state EE to state OE : go from EE to OE or first go from EE to OE, then from OE to EE and then back to OE. So the regular expression for this device is
R*P(Q + TR*P)*.
2012年11月24日星期六
Regex
It is in week 11 now! Almost finish this course!
Now we are learning Regex and NFSA and DFSA. The last assignment is coming and it is about time comlexity and FSAs.
Most of the lecture material was not difficult to understand, but I was kind of confused by the difference between DFSA and NFSA. What I did this time was to look up definitions on the textbook. On the textbook, it said:
A deterministic finite state automaton (DFSA) is a mathematical model of a machine which, given any string input x, accepts or rejects x. The automaton has a finite set of states. including a designated initial state and a designated set of accepting states. While the definition of NFSA was that: In a DFSA, a given state and current input symbol uniquely determine the next state of the automaton.
To my understanding, the difference is that: in DFSA, the state only depends on the input, but in NFSA, the state depends on both the current input and also the given state.
BTW, I like drawing NFSA or DFSA, it was much more interesting than just to prove something using Induction or prove the correctness of a funciton.
Now we are learning Regex and NFSA and DFSA. The last assignment is coming and it is about time comlexity and FSAs.
Most of the lecture material was not difficult to understand, but I was kind of confused by the difference between DFSA and NFSA. What I did this time was to look up definitions on the textbook. On the textbook, it said:
A deterministic finite state automaton (DFSA) is a mathematical model of a machine which, given any string input x, accepts or rejects x. The automaton has a finite set of states. including a designated initial state and a designated set of accepting states. While the definition of NFSA was that: In a DFSA, a given state and current input symbol uniquely determine the next state of the automaton.
To my understanding, the difference is that: in DFSA, the state only depends on the input, but in NFSA, the state depends on both the current input and also the given state.
BTW, I like drawing NFSA or DFSA, it was much more interesting than just to prove something using Induction or prove the correctness of a funciton.
2012年11月10日星期六
Midterm 2
Just finished my midterm two!
It was Ok~ I was so busy this week so I did not have lots of time prepare for it. But I think it will be fine since I did not have questions remained from the lectures before.
I got 100% on my assignment one! I am sooooooooo happy!!!!
Hope my assignment two will be still good!
It was Ok~ I was so busy this week so I did not have lots of time prepare for it. But I think it will be fine since I did not have questions remained from the lectures before.
I got 100% on my assignment one! I am sooooooooo happy!!!!
Hope my assignment two will be still good!
2012年11月3日星期六
Assignment 2
I just submitted the second assignment. In general, I found the second assignment was harder than the first one.
There were two questions in this assignment. Sounds not much, but each question was very long. The first question asked us to unwind first and then prove the closed form. It was very much like a question that was in one of the tutorial. So what I did was to review the tutorial question first and then try to do the question myself. The unwinding was not very complicated for me and since I was pretty clear with Simple Induction and Complete Induction, I solved the first question without too much difficulties.
The second question was about what we learnt in the last week -- time conplexity. I was so glad that I solved all questions that I didn't understand last week so now I was very clear about what steps should I do. If I did not fix my problem last week, I would be confused about how to do this question and it was going to take me a lot of time if I googled online or read through all the pages on the textbook. So, Never Put Off Until Tomorrow What You Can Do Today. ^_^
This week we mainly learnt about proving the correctness of a function.
To prove the correctness of a function. We need to prove that under the assumption that precondition holds, the function terminates and the post condition holds. To prove the function terminates, we have to construct a decreasing sequence in N and then use well-ordering principle to prove that there is a smallest value in N so that the loop will finally terminate.
The second midterm is in next week. I need to read through the text book as much as I can and clear all my questions before the test. Oh~ and do not make the same mistakes again as in Midterm test one. Cheer up and be ready! ^_^
2012年11月1日星期四
Midterm Paper Back
Got my midterm back! But I was not so happy with my grade.
The questions were not so hard. I lost marks mostly for the structure and the induction hypotheses. I think I am going to professor's office hour and ask for suggestions. Hope I won't make the same kind of mistake in the second midterm test.
Looking forward to get my assignment one back!
2012年10月27日星期六
Master Theorem
In week 7 we learnt about Master Theorem.
I found Master Theorem was very interesting and it was an easier way to find the upper and lower bound. But one problem (at least it was a problem for me) was that I had to remember the three different cases. I liked to use method in week 6 better than this because I did not like to cram something without knowing how to get the conclusion.
Have a nice week!
订阅：
博文 (Atom)