Monday, December 1, 2008

Pumping Lemma, CFGs

The end of the term is very close. Time passes way too fast...

I realized that the pumping lemma could be difficult so I did some pre-reading before the lecture. Unfortunately, I still don't really get it after the lecture. The test is this friday, so I'm going to be going over it right after I finish this.

Unfortunately I think I'm also rather unclear, or have a lack of intuitive understanding of the regularity of a language. Is it generally any language that requires some "memory" to represent as a regex or FSA?

Context-free Grammars are interesting.
It's obvious that we've only seen the tip of the iceberg in this area, and I'm quite interested in how the theory can be extended and applied in practical usage. Unfortunately (or maybe fortunately,) I won't have to get too deep into this, as I'm not planning to take compilers or programming language courses.

***edit
After looking at the course notes and lecture notes. I find the lecture notes much clearer intuitively. But the course notes has great stuff too. With the combination of going through both I *think* I understand how proof of regularity by the pumping lemma works now.

For languages which have some pumping length for which the pumping lemma holds for all strings in the language, it is regular.
For languages which have arbitrarily large pumping lengths, and so no single pumping length works for all strings in the language, the language is not regular.

I hope that understanding is correct.

No comments: