CMSC 28000: Introduction to Formal Languages (Spring 2024)
General information
- Instructor
- Timothy Ng (timng@uchicago.edu)
- Class meetings
- MWF 10:30–11:20, Stuart 105
- MWF 11:30–12:20, Stuart 105
- Links
-
Overview
This course explores the mathematical foundations of computation. How do we quantify computational power? Are there limits on the kinds of problems that computers can solve? To answer such questions, we examine the curious connection between computation and mathematical linguistics.
Communication
There are a number of different ways we'll be communicating about the class.
- Course materials
- Lecture notes will be made available via this course website. The course website also contains basic information about the course (i.e. you can treat this like a syllabus).
- Discussion and announcements
- We will use Ed Discussion for course discussion and announcements. Restricted course materials will also be posted here.
- Coursework and grades
- We will use Gradescope for distributing and receiving coursework. Your grades will also be available here.
- Office hours
- Office hours are times when the course staff are available for you. The instructor and teaching assistants will have scheduled office hours. While most students use this as an opportunity to ask about coursework, you're free to ask about or discuss things that are related directly or indirectly with the course.
- Lectures
- Lectures are often the first point at which students will be exposed to new ideas and material. They will cover material that is necessary for success in the course. However, lectures alone may not be sufficient for all students. It is not expected that students will master the material learned in lecture without significant review, inquiry, and practice outside of lecture.
Course materials and objectives
The following is a list of topics that will be covered in the course.
- Regular languages and finite automata
- Deterministic and non-deterministic finite automata, closure properties, regular expressions, Brzozowski derivatives, the pumping lemma for regular languages, DFA minimization, the Myhill-Nerode theorem.
- Context-free languages and grammars
- Context-free grammars, normal forms, the pumping lemma for context-free languages, pushdown automata, closure properties.
- Decidable and undecidable languages and problems
- Turing machines, the Church-Turing thesis, computability, undecidability, the Halting Problem, reductions.
Upon completion of the course, students should be able to
- Describe how computation can be modeled mathematically.
- Describe how computational problems can be described as formal languages.
- Classify formal languages according to their complexity.
- Describe and transform formal languages across their different representations.
- Describe the limits of various computational models.
Text
There is no required textbook for this course. Lecture notes will be made available. Lectures are based largely on the following sources—you can consider one of these if you're looking for a reference.
- Dexter Kozen. Automata and Computability (1997). This is available online for free via the UChicago Library.
- Michael Sipser. Introduction to the Theory of Computation, 3rd ed. (2012). Any edition of this would be a solid reference.
The lectures also incorporate material from the following texts, to a lesser extent.
- John Hopcroft and Jeffrey Ullman. Introduction to Automata Theory, Languages, and Computation, 1st ed. (1979). (This resource is now out of print and subsequent editions do not have the same material.)
- Jeffrey Shallit. A Second Course in Formal Languages and Automata Theory (2008).
- Jacques Sakarovitch. Elements of Automata Theory (2009).
You can use the UChicago Library proxy to access online resources via the library when you are off-campus. Some of these items are also available on reserve in Crerar Library.
If you refer to one of these texts, keep in mind that some notation and definitions will vary. In such cases, the course notes will take precedence.
Coursework and evaluation
Your computed grade in this course will be determined by the following coursework components.
- Weekly problem sets, worth 50% in total.
- A midterm examination, worth at most 25%.
- A final examination, worth at least 25%.
Problem sets
Problem sets will be released on Wednesdays and will be due on the following Thursday at 8:00 pm (20:00) Central.
Problem sets will be distributed and submitted via Gradescope.
- Submissions must be typed. $\LaTeX$ is the preferred and recommended method for preparing your submission but it is not required. No handwritten submissions of any kind will be accepted—this includes digitally handwritten submissions, such as those prepared on a tablet.
- Take the opportunity to learn how to typeset mathematics with $\LaTeX$! In addition to many resources you can find online, all of the $\LaTeX$ commands used in the lecture notes is easily accessible by right-clicking on any formula, and selecting "Show Math As" $\rightarrow$ "TeX Commands" from the context menu.
Collaboration, citation, and academic integrity
The purpose of problem sets is to give you the opportunity to practice working through the process of solving problems and to receive feedback on that process. The work that you hand in to be graded is expected to be your own. Why is this important?
- When you submit a piece of work, you are claiming that it is a product of your understanding of the material.
- Your work is subject to critique. It is important that your work represents your understanding so that the feedback you receive will be useful.
- Authorship is not only about receiving credit for work, but also accountability. You should not submit any work for which you do not want to be held responsible for.
Be sure to acknowledge your collaborators and any sources beyond course materials that you may have used.
- If you choose to work with others, you must list your collaborators. You may only work with other students in the class. Your collaboration should be to a degree that your writeups are substantially different. It is not acceptable that solutions are largely copies of each other.
- You should not look up solutions to assigned problems, online or otherwise. This includes question and answer forums, homework websites, and other publicly available materials from other courses in the department or at other institutions. Be aware that if you can find a solution online, the course staff can too.
- Since the purpose of the problem sets is to give you the opportunity to practice working through the process of solving problems and writing mathematics, you should not use language models to generate your submissions, whether in part or in whole.
- If you use a source beyond course materials, the source must be a published source—either a book or journal article—and full citation must be given.
- If you are not sure about whether something is permissible, you should err on the side of caution and ask the instructor.
It is your responsibility to be familiar with the University’s policy on academic honesty. Instances of academic dishonesty will be referred to the Office of College Community Standards for adjudication. Following the guidelines above on collaboration and citation should be sufficient, but if you have any questions, please ask me.
How solutions are graded
Your solutions on problem sets and exams are judged on the following basis:
- Validity. Your solution will be judged on its correctness. This includes whether a method was applied correctly, calculations are correct, and proof steps follow the rules of logic.
- Presentation. Your solution will be judged on its presentation as it relates to readability and fluency. A solution may be correct, but is unable to communicate this fact to the reader. A readable solution should guide the reader through the argument, providing the appropriate explanation and justification. By fluency, we mean the correct use of the language of mathematics. This includes the proper use of established terminology and notation.
Grading of problems is based on the overall quality of the solution. Clearly, solutions need to be valid in order to be evaluated highly, but a completely valid solution that is not readable will still be evaluated poorly. Furthermore, grades are assigned as a qualitative evaluation of the work and not a quantitative accounting of the work. This appears as a 4-point scale on Gradescope.
Generally, the overarching principle that guides the grading is: How much work and guidance is needed for you to revise your submission into something that is Excellent?
- 4 (Excellent). The solution is correct and readable. The solution is not necessarily perfect—it may have a few trivial flaws in logic or presentation that can be easily corrected.
- 3 (Good). The solution is generally correct and readable and has some minor flaws in logic or presentation—often there is one last "step" that is missing. Understanding of the problem has been clearly demonstrated. The solution and presentation can be improved quickly with a few suggestions—for instance, a bit more generalization or one more logical step that needs to be taken.
- 2 (Borderline). The solution could be correct and readable but has a major flaw in logic or presentation. There is evidence that there is some understanding of the problem and the solution is on the right track or has the right idea. The solution and presentation can be improved with some guidance and substantial revisions.
- 1 (Needs revision). The solution is generally not correct or not readable. It is not clear that the problem was understood and/or the presentation of the solution is heavily flawed. In either case, there is a significant gap in understanding or execution. The solution should be revised with some guidance.
- 0 (Incomplete). The solution was not submitted or is clearly incomplete. Submissions that are graded Incomplete are ineligible for resubmission.
The assigned grade is the grader’s judgement of whether the solution meets the standards of the class. In addition to the assigned grade, the grader is expected to provide detailed feedback, addressing specific flaws in the submitted work that can and should be improved in future work.
Resubmission
Part of the learning process is identifying and correcting mistakes. After your submissions have been graded and returned to you, you will have the opportunity to use the feedback you receive to revise and resubmit your work.
Instructions for how to prepare resubmissions will be provided when problem sets become available for resubmission.
Regrade requests
You may submit a regrade request in the event of an error by the grader. That is, if the feedback provided by the grader is a factual error, you may request a review of the grading. Please indicate the source of the error in this case.
We will not consider regrade requests concerning disagreement with a grader’s evaluation of your work. In such cases, you should consider the feedback that was given and apply it towards revision and resubmission of your work.
Lectures
Section numbers refer to Kozen unless otherwise stated.
- March 18
- The theory of computation [1, 2]
- March 20
- Strings, languages, machines [2, 3]
- March 22
- Finite automata, divisibility [3, 4]
- March 25
- Closure properties of DFA languages [4]
- March 27
- Nondeterministic finite automata [5]
- March 29
- The power of nondeterminism [6]
- April 1
- Regular languages and regular expressions [7, 8]
- April 3
- Finite automata and regular expressions [8, 9]
- April 5
- Derivatives of regular expressions [Sakarovitch 4.4]
- April 8
- Non-regular languages [11, 12]
- April 10
- The Myhill–Nerode theorem [15, 16]
- April 12
- Myhill–Nerode and minimal DFAs [16, 13]
- April 15
- Grammars and context-free languages [19]
- April 17
- Midterm examination
- April 19
- Derivations, Chomsky normal form [19, 21]
- April 22
- Chomsky normal form, recognition [21, 27]
- April 24
- Pushdown automata [23]
- April 26
- Simulating grammars via PDAs [E, 24]
- April 29
- Simulating PDAs via grammars [25]
- May 1
- Non-context-free languages [22]
- May 3
- Computability and Turing machines [28, 29]
- May 6
- Variations of Turing machines [30]
Accessibility
Students with disabilities who have been approved for the use of academic accommodations by Student Disability Services (SDS) and need reasonable accommodation to participate fully in this course should follow the procedures established by SDS for using accommodations. Timely notifications are required in order to ensure that your accommodations can be implemented. Please meet with me to discuss your access needs in this class after you have completed the SDS procedures for requesting accommodations.