Just had the term test today. It went better than I expected since I wasn't too prepared on NFSAs. I got lucky there wasn't a question on it. There was one question on DFSAs which was fairly easy since no proof was required. The second and the third question were about regular expressions and those I have had enough practise with and didn't trouble me much at all.
I took a look at NFSAs after the test however and it doesn't seem as bad as I had thought. Apparently they are equivalent to DFSAs, but a lot simpler to construct and deal with. My main concern was those seemingly "random" choices that are allowed to be made. But now I see that it's just a different form of expression and it's not like a computer randomly chooses one. It's just different allowed paths that can be taken. For some reason NFSAs actually seem more familiar to the more tangible handling of the regular expressions that we did in CSC207. Anyways it looks like I'm not too badly prepared for next week. I just need to look through NFSAs a little more in depth and also take a look at the Pumping Lemma and I should be set for the exam.
This is my last blog post for this course I suppose. I wasn't exactly jumping for joy about this course in the beginning since I'm more into algorithms that are a little more practical than the purely theoretical side of computer science, but I actually quite enjoyed it and I must say it has made me more curious about what CSC263 has in store. Danny was an excellent prof and I hope I get to take a class by him again.
Friday, December 5, 2008
Wednesday, December 3, 2008
FSA, regex and CFG
I've been out of touch with the SLOGs lately. I guess here I'm going to reflect on everything that happened in the last four weeks.
To start off, despite them being able to represent the same things, I still find it sort of hard to convert regexes into FSAs and vice versa fluently. However, the feeling I got from Danny's handling of these two is that certain languages are easier to handle by one of them and others are easier for the other one. The first example he showed us with an FSA clearly demonstrates this. The language of binary strings with an even number of zeros and an odd number of ones is quite difficult to find a regular expression for, but an FSA can be built very simply. Individually, i.e. without the worry of coverting from one to the other, I think I have a pretty good handle on both methods. This is especially true for regular expressions, since I got quite a lot of practice dealing with them in the second assignment for CSC207.
I'm not too clear on NFSAs however. I missed some important lectures on that topic and now I'm behind. Hopefully I will be able to catch up fully before Friday's test. It doesn't seem very clear to me on how to decide with path to take when there is more than one option. Also another thing that throws me off is the necessity to include epsilon transitions for the start and ending states. I was unable to solve the last question of Assignment 3, but this topic I have yet to study properly so hopefully things will clear up soon.
And then we covered context-free-grammars. These seem pretty straightforward, but I'm having trouble understanding why they are equivalent to PDAs. In a PDA, we can use a stack to remember certain information. But where is this memory feature in CFGs? PDAs are cool though. I liked how it could handle binary strings with the same number of 0s and 1s. A friend of mine in 3rd year computer science told me about this exact same language and how an FSA or regular expression cannot handle it and apparently it takes a Turing Machine to do this. But as it turned out, all it takes is the stack feature of PDAs.
To start off, despite them being able to represent the same things, I still find it sort of hard to convert regexes into FSAs and vice versa fluently. However, the feeling I got from Danny's handling of these two is that certain languages are easier to handle by one of them and others are easier for the other one. The first example he showed us with an FSA clearly demonstrates this. The language of binary strings with an even number of zeros and an odd number of ones is quite difficult to find a regular expression for, but an FSA can be built very simply. Individually, i.e. without the worry of coverting from one to the other, I think I have a pretty good handle on both methods. This is especially true for regular expressions, since I got quite a lot of practice dealing with them in the second assignment for CSC207.
I'm not too clear on NFSAs however. I missed some important lectures on that topic and now I'm behind. Hopefully I will be able to catch up fully before Friday's test. It doesn't seem very clear to me on how to decide with path to take when there is more than one option. Also another thing that throws me off is the necessity to include epsilon transitions for the start and ending states. I was unable to solve the last question of Assignment 3, but this topic I have yet to study properly so hopefully things will clear up soon.
And then we covered context-free-grammars. These seem pretty straightforward, but I'm having trouble understanding why they are equivalent to PDAs. In a PDA, we can use a stack to remember certain information. But where is this memory feature in CFGs? PDAs are cool though. I liked how it could handle binary strings with the same number of 0s and 1s. A friend of mine in 3rd year computer science told me about this exact same language and how an FSA or regular expression cannot handle it and apparently it takes a Turing Machine to do this. But as it turned out, all it takes is the stack feature of PDAs.
Subscribe to:
Comments (Atom)