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 computation. The second is programming languages, which studies different abstractions of computational processes. Both of these study the representation of computing. They are further linked because compilers are implemented using tools from automata theory. We will learn about each of these areas and their linkages. The course will features a mixture of written work and programming, with the automata portion being primarily written and the programming languages portion being primarily implemented in ML, a functional programming language we will learn in this course.
We meet Monday, Wednesday, Thursday, and Friday during 2nd period (9:20-10:30) in SMC-D205. We will sometimes move into the Crash and Burn lab (SMC-A215).
This course does not have a textbook since no single book covers the entire course. My lectures will draw on material from the following books, which I have placed on reserve:
If you want a reference on ML, I suggest looking at the resources at http://www.smlnj.org/doc/literature.html. You can also download your own copy of Standard ML of NJ (the version we're using) from their website, http://www.smlnj.org/.
Week 1: Pic and "Little languages". Deterministic finite automata (DFAs).
Week 2: Introduction to ML. Non-determinism (NFAs).
Week 3: Regular expressions. Tail recursion. Higher-order functions.
Week 4: Pumping lemma for regular languages. Exceptions. Lex.
Week 5: Context-free grammars. Grammar normal forms. Midterm.
Week 6: Ambiguity. Associativity. Order of operations. Parsing.
Week 7: Modules. Functors. Programming language presentations.
Week 8: Pumping lemma for CFLs. Continuations. Turing machines.
Week 9: Undecidability. Rice's Theorem. Type inference.
Week 10: Concurrency.
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.
I assign extra credit problems infrequently. I will however give extra credit for attending colloquium talks sponsored by the CS department (possibly other departments, depending on the content of the talk) and submitting a short writeup about the talk. Give a quick summary and any impressions you had in a couple of paragraphs (~1 page). This offer applies to any qualifying talk you are not otherwise getting credit to attend and is due within a week of the talk (slight extensions possible, but I want you to still remember the talk...).
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 your 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% |
| Language project | 15% |
| Midterm | 20% |
| Final | 20% |
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. It will not be stricter than the "standard" 90/80/70/60 grading and may be more generous. 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.