Website: http://courses.knox.edu/cs306
This course covers parts of two courses from a traditional CS curriculum. The first is automata theory, which looks at a series of computational models as a way of studying the limits of computing. The second is programming languages, which studies different abstractions of computational processes. In this course, we combine these topics by using automata as tools to construct parsers for different points in the design space of possible languages.
We meet Monday, Wednesday, Thursday, and Friday during 5th period (1:20-2:30) in SMC-A207. We will sometimes move into the Crash and Burn lab (SMC-A215).
Class will not be held on October 12 to facilitate attending Reflections and Projections.
This course does not have a textbook. I have placed the following relevant sources on reserve in the SMC library: (these may not all have arrived at the beginning of the semester)
We will be using the automata software JFLAP. If you want more instruction on it than provided in class, you can refer to the book above or the online tutorial available at its website. (The two are similar.)
Week 1: Review of deterministic finite automata. Regular languages.
Week 2: Non-determinism (NFAs). Regular expressions. Closure properties of regular languages.
Week 3: Non-regular languages. Pumping lemma for regular languages. State minimization.
Week 4: Context-free grammars. Push-down automata. Exam 1.
Week 5: Grammar normal forms. Closure of context-free languages (CFLs). Pumping lemma for CFLs.
Week 6: Grammars for programming languages. Ambiguity. Associativity. Exam 2.
Week 7: Parsing.
Week 8: Names. Binding. Garbage collection.
Week 9: Assignment. Control structures.
Week 10: Other programming models (OO, functional, logical).
Be aware that anything you submit may be used in class as an example. The purpose of this is to provide examples and material for discussion, not to embarrass you. I will endeavor to use these examples anonymously by removing names and any other identifying features.
You should plan on submitting all work by the due date, but I know this is not always possible. Therefore, you will get two "late days" that may be used on homework assignments during the term. Each allows you to submit one homework 24 hours late without penalty. They can be used for the same or different assignments. To use them, write a note on the top of your submission. Late assignments without such a note will lose 10% of their points for each 24 hours they are late. Late submissions will not be accepted once solutions have been posted so let me know if you intend to work on something past its normal deadline. Individual extensions beyond these two days will require extraordinary circumstances.
Regular attendance is expected, but there will not be a specific penalty for missing lecture. You are responsible for your own education. This means that you need to find someone to turn in homework if you are absent on the due date and you must find a way to learn the material covered during absences. In addition, please send me an email if you will be missing class so I know what is going on.
Exams in this class must be completed individually. You are allowed to talk with others about homework and encouraged to work together in small groups (2-3 students). When you do this, however, you must do two things:
The same policies apply to getting help from inanimate sources. If you use the web or a textbook other than the one we're using, you must cite this source. As in collaborations with another person, you are expected to write you own solution; do not copy text or code from any source. In addition, you may look at other sources for examples or conceptual help, but not actual solutions. Some problems assigned for this class may have been previously assigned to other classes, but you are expected not to deliberately seek solutions. (If you come across one accidently, let me know and I will give you a modified assignment.)
Please feel free to contact me if you have any questions about this policy.
At the end of the term, all of your work will combined into an overall course percentage based on the following weights:
| Homework | 45% |
| Exams | 30% (15% each) |
| Final/final project | 25% |
Note that homework makes up a very high percentage of our course grade. Be sure to keep up. I strongly recommend that you start assignments early so you can ask questions if you run into difficulty.
The range of scores mapping to each grade will be determined at the end of the term. In general, spend your time learning the material rather than worrying about your grade, but feel free to talk with me if you are concerned about it.