So, tomorrow's lecture will be the last one this semester. Time surely passes quickly; I can still remember my first 236 lecture in September. It's been an exciting ride, especially since this semester has been the most hectic one for me.
About the last assignment: strangely, I find that the first question is the most tricky one. I could understand why we need at least 16 states for the DFSA, but it took me a while to figure out how to structure the proof (using contradiction). I hope the logic I came up with is valid.
As for the rest of the course, I think I should have enough time to get to grip with NFSA. Thank God for large gap between the last day of lecture and our final exam.
Wednesday, November 28, 2012
Wednesday, November 21, 2012
Tutorial 7
Just skimmed through the handout of tutorial 7. My thoughts so far:
1. Prove or disprove that if RS == SR => R == S (let this statement be our predicate)
Let S and R be two regular expressions
To disprove, we only need to find a counter example.
Let R = (0 + 1)*
and S = 1*
So, RS = (0 + 1)*1* and SR = 1*(0 + 1)*
Note that the string "01" is accepted by both RS and SR, so RS == SR
But, R != S, so this is a contradiction!
Therefore we've disproved the statement
2. Devise a regex R for all strings of {0, 1}* that start and end with the same bit (e.g. 1001101, 01000, etc.)
R1 = 1(0 + 1)*1 -> a string that starts with 1, followed by 0 or more occurences of {0, 1}, ends with 1
R2 = 0(0 + 1)*0 -> a string that starts with 0, followed by 0 or more occurences of {0, 1}, ends with 0
R = R1 + R2 = (0(0 + 1)*0) + (1(0 + 1)*1) -> R1 or R2
Proof of correctness:
I still don't know how to write a formal proof for this regex. I'll update this post sometime after the tutorial tomorrow.
1. Prove or disprove that if RS == SR => R == S (let this statement be our predicate)
Let S and R be two regular expressions
To disprove, we only need to find a counter example.
Let R = (0 + 1)*
and S = 1*
So, RS = (0 + 1)*1* and SR = 1*(0 + 1)*
Note that the string "01" is accepted by both RS and SR, so RS == SR
But, R != S, so this is a contradiction!
Therefore we've disproved the statement
2. Devise a regex R for all strings of {0, 1}* that start and end with the same bit (e.g. 1001101, 01000, etc.)
R1 = 1(0 + 1)*1 -> a string that starts with 1, followed by 0 or more occurences of {0, 1}, ends with 1
R2 = 0(0 + 1)*0 -> a string that starts with 0, followed by 0 or more occurences of {0, 1}, ends with 0
R = R1 + R2 = (0(0 + 1)*0) + (1(0 + 1)*1) -> R1 or R2
Proof of correctness:
I still don't know how to write a formal proof for this regex. I'll update this post sometime after the tutorial tomorrow.
Monday, November 19, 2012
Catching Up
So, it's been a while since I last posted here. The last few weeks had been incredibly hectic, with midterms, assignments, and interviews I had to attend. Anyway, this is the first time in the past few weeks where I had no midterm or assignment due. Thought I'd use it to start off early with assignment 3. Partly because unlike in assignment 2, I can actually spend more time on this assignment if I start early. I didn't do as well as I would've liked in assignment 2 due to the lack of time to go over it. As a result, the proofs were flawed or incomplete.
After skimming through it, it looks like I need to spend more time to learn more about DFSA. I couldn't attend the lecture & tutorial session where it was discussed, so I need to read up more on the issue to get better understanding of it.
I hope to finish this assignment by the end of this week, which should leave me plenty of time before the due date to go over it as needed. This might seem drastic, but one thing I learn from being in PEY this year is that companies like to call you for interviews at the very last minute. You may think that you have enough time allocated to do your assignments, but if you get the call, then your plans will be thrown into disarray. That happened to me last week, and with the amount of work due at the end of the semester (3 CSC assignments + 1 midterm + 1 presentation, all due between November 30 and December 4), I have to be way more conservative with my time allocation.
After skimming through it, it looks like I need to spend more time to learn more about DFSA. I couldn't attend the lecture & tutorial session where it was discussed, so I need to read up more on the issue to get better understanding of it.
I hope to finish this assignment by the end of this week, which should leave me plenty of time before the due date to go over it as needed. This might seem drastic, but one thing I learn from being in PEY this year is that companies like to call you for interviews at the very last minute. You may think that you have enough time allocated to do your assignments, but if you get the call, then your plans will be thrown into disarray. That happened to me last week, and with the amount of work due at the end of the semester (3 CSC assignments + 1 midterm + 1 presentation, all due between November 30 and December 4), I have to be way more conservative with my time allocation.
Subscribe to:
Posts (Atom)