CMSC 28000: Introduction to Formal Languages (Winter 2021)
General information
- Instructor
- Timothy Ng (timng@uchicago.edu)
- Teaching assistants
- Tiago Royer (royer@uchicago.edu)
- Jesse Stern (jesseastern@uchicago.edu)
- 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
This class is being offered remotely and asynchronously. There are a number of different ways we'll be communicating about the class.
- Course materials
- Lecture notes and links to lecture videos 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 Campuswire for course discussion and announcements. Restricted course materials and Zoom meeting information will also be posted here.
- Coursework and grades
- We will use Gradescope for distributing and receiving coursework, such as problem sets and exams. Your grades will also be available here.
Class meetings
Lectures will be streamed live on Mondays, Wednesdays, and Fridays at 10:20–11:10 am Central. Links to each stream will be posted before they begin. The stream will be archived and available for viewing shortly afterwards. Note that there is no requirement or expectation for students to watch or participate in lectures during the live stream.
Topics
- Regular languages
- Deterministic and non-deterministic finite automata, closure properties, regular expressions, the pumping lemma for regular languages, DFA minimization, the Myhill-Nerode theorem, derivatives.
- Context-free languages
- Context-free grammars, normal forms, the pumping lemma for context-free languages, pushdown automata, closure properties.
- Decidable and undecidable languages
- Turing machines, the Church-Turing thesis, computability, undecidability, the Halting Problem, reductions.
Text
There is no required textbook for this course. Lecture notes will be made available. Lectures incorporate material from the following sources. You can consider one of the first two if you're looking for an alternative 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.
- John Hopcroft and Jeffrey Ullman. Introduction to Automata Theory, Languages, and Computation, 1st ed. (1979). This edition has long been out of print. The 3rd edition with Motwani is currently available, but has had a lot of stuff taken out.
- Jeffrey Shallit. A Second Course in Formal Languages and Automata Theory (2008). Selected topics.
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.
Evaluation
Your computed grade in this course will be determined by the following coursework components.
- A take-home final exam, to be completed during finals week. Let $F$ be the grade earned on the final exam. The weight of the final exam depends on the completion of other coursework.
- Weekly problem sets, worth 60% in total. Let $P$ be the average of the grades earned on problem sets.
- Biweekly personal reflections each worth 1%. Let $R$ be the number of completed reflections.
There is no midterm exam. Let $S = (60\% \times P) + (1\% \times R)$. Then your computed grade will be obtained via the following formula:
\[ S + F \times (100\% - S). \]
Problem sets
- Students are expected to write up solutions to problem sets individually, but may work together. Be sure to acknowledge your collaborators and any sources beyond course materials that you may have used.
- Problem sets will be posted on Wednesdays and will be due on the following Wednesday at 8:00 pm (20:00) Central.
- Please ensure that submissions are legible. See this guide for submitting on Gradescope.
Lectures
- January 4
- Introduction and course information
- January 11
- Computation, strings, and languages
- January 13
- Finite automata
- January 15
- DFA languages, closure properties
- January 20
- String operations, nondeterminism
- January 22
- The subset construction, $\varepsilon$-NFAs
- January 25
- Regular languages
- January 27
- Kleene's Theorem
- January 27
- Brzozowski Derivatives
- February 1
- Nonregular Languages
- February 3
- Myhill–Nerode
- February 5
- DFA Minimization
- February 8
- Context-Free Languages
- February 10
- Chomsky Normal Form
- February 12
- Recognition and Characterization of CFLs
- February 15
- Pushdown Automata
- February 17
- Equivalence of context-free grammars and pushdown automata
- February 19
- Deterministic context-free languages and parsing
- February 22
- Non-context-free languages
- February 24
- Turing Machines
- February 26
- Variations of Turing Machines
- March 1
- Decidability and decision problems on formal languages
- March 3
- Recognizability and undecidability
- March 5
- More undecidability
- March 8
- Reduction
- March 10
- Undecidable problems about CFLs
Academic integrity
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 the Provost for adjudication. Following the guidelines above on collaboration and citation should be sufficient, but if you have any questions, please ask me.
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.