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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment